菲尼克斯正在他的后院采摘浆果。有 $$$n$$$ 灌木,每个灌木都有 $$$a_i$$$ 红色浆果和 $$$b_i$$$ 蓝色浆果。
每个篮子可容纳 $$$k$$$ 浆果。但是,菲尼克斯决定每个篮子只能包含来自同一灌木的浆果或相同颜色(红色或蓝色)的浆果。换句话说,篮子中的所有浆果必须来自同一灌木或/和具有相同的颜色。
例如,如果有两个灌木,第一个灌木中有 $$$5$$$ 红色浆果和 $$$2$$$ 蓝色浆果,第二个灌木中有 $$$2$$$ 红色和 $$$1$$$ 蓝色浆果,则 Phoenix 可以完全填满 $$$2$$$ 篮子的容量 $$$4$$$:
- 第一个篮子将包含来自第一个灌木的 $$$3$$$ 红色浆果和 $$$1$$$ 蓝色浆果;
- 第二个篮子将包含来自第一个灌木的 $$$2$$$ 剩余红色浆果和来自第二个灌木的 $$$2$$$ 红色浆果。
帮助菲尼克斯确定他能完全装满的篮子的最大数量!
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$ 1\le n, k \le 500$$$)——分别是灌木的数量和篮子的容量。
接下来的 $$$n$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$0 \le a_i, b_i \le 10^9$$$) — 分别是第 $$$i$$$ 灌木中红色和蓝色浆果的数量。
输出
输出一个整数——Phoenix能装满的篮子的最大数量。
示例
输入 #1
2 4 5 2 2 1
输出 #1
2
输入 #2
1 5 2 3
输出 #2
1
输入 #3
2 5 2 1 1 3
输出 #3
0
输入#4
1 2 1000000000 1
输出#4
500000000
注意
上面描述了第一示例。
在第二个示例中,Phoenix 可以使用第一个(也是唯一一个)灌木中的所有浆果完全装满一个篮子。
在第三个示例中,Phoenix 无法完全装满任何篮子,因为每个灌木中的浆果少于 $$$5$$$,红色浆果总数少于 $$$5$$$,蓝色浆果总数少于 $$$5$$$。
在第四个例子中,菲尼克斯可以将所有红色浆果放入篮子中,留下额外的蓝色浆果。