← 返回题目列表

Codeforces · 1348/E

E. 凤凰和浆果

中文机器翻译题面 查看原题

菲尼克斯正在他的后院采摘浆果。有 $$$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$$$。

在第四个例子中,菲尼克斯可以将所有红色浆果放入篮子中,留下额外的蓝色浆果。