思路解析

把第 $i$ 个长方形放下时，只需在两种朝向里选一种：

• 令高度为 $x_i$、宽度为 $y_i$；
• 或令高度为 $y_i$、宽度为 $x_i$。

限制是高度 $\le m$。显然每个长方形彼此独立，总长度就是各自选择后的宽度之和，因此问题可分解为对每个 $i$ 局部做最优选择。

对单个长方形的最优宽度 $w_i$：

题目内容

小美有 $n$ 个长方形，第 $i$ 个长方形的两条边长分别为 $x_i,y_i$ ；

小美拥有一个仅包含第一象限的平面直角坐标系；

小美希望将这 $n$ 个长方形按顺序(可以旋转)放置在 $x$ 轴上，不允许重叠，并且每个长方形放置后的高度不超过 $m$ ，保证 $max(min(x_i,y_i))≦m$ ；

请问，在满足上述条件的前提下，小美最少需要占用 $x$ 轴的长度是多少?

输入描述

第一行输入两个整数 $n,m(1≦n≦2×10^5;1≦m≦10^9)$ ，分别表示长方形的个数和允许的最大高度；

接下来 $n$ 行，每行输入两个整数 $x_i,y_i(1≦x_i,y_i≦10^9)$ ，分别表示第 $i$ 个长方形的两条边长。

输出描述

输出一个整数，表示在每个长方形高是不好过 $m$ 的情况下，所需占用的最短 $x$ 轴长度。

样例1

输入

3 4
1 2
2 5
4 2

输出

8

说明

• 第 $1$ 个长方形可用高度较小的一条边放置，高度 $2≤ 4$ ，占用长度 $min(1,2)=1$ ；

• 第 $2$ 个长方形仅能以高度 $2$ 放置，占用长度 $5$ ；

• 第 $3$ 个长方形可用较小的一条边放置，占用长度 $min(4,2)=2$ ；

因此总长度为 $1+5+2=8$ 。