分数: 233 分
问题陈述
高桥和青木正准备出售 N 学校文化节展位上的各种糖果。
对于 i第一种甜点,高桥带来 A_i 件和青木带来 B_i 件。同一类型的糖果无论是谁带来的都无法区分,因此它们被视为总和 A_i + B_i 件。
所有这些糖果都必须装进盒子并运送到销售摊位。
可以根据需要提供尽可能多的盒子。每个盒子之间可以容纳 1 和 K 糖果(含),但不同种类的糖果不能放在同一个盒子里。
如果某种类型的糖果总数为 0,该类型不需要使用盒子。
求装满所有糖果所需的最少盒子数量,且不剩任何糖果。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^9
- 0 \leq A_i \leq 10^9
- 0 \leq B_i \leq 10^9
- 所有输入值均为整数
- 在这些约束下,答案适合 64 位有符号整数
输入
输入按以下格式给出。
N K A_1 B_1 A_2 B_2 \vdots A_N B_N
第一行包含糖果的种类数量 N 以及每盒糖果的最大数量 K,用空格分隔。
以下各项 N 行包含,对于 i第类型,件数 A_i 高桥准备及件数 B_i 由 Aoki 编写,以空格分隔。
输出
在一行上打印出携带所有糖果所需的最小盒子数量。
示例输入 1
3 5 1 2 4 0 3 5
示例输出 1
4
示例输入 2
4 3 0 0 1 2 3 0 2 5
示例输出 2
5
示例输入 3
8 7 2 3 7 0 6 6 0 5 14 1 8 13 0 0 20 4
示例输出 3
15
示例输入 4
15 10 100 0 0 1 9 9 10 10 123 456 999999999 1 500000000 500000000 17 23 0 0 42 58 1000000000 1000000000 314159265 271828182 5 4 19 0 0 999999999
示例输出 4
558598835
示例输入 5
1 1000000000 0 0
示例输出 5
0