← 返回题目列表

AtCoder · awc0042_a

A. 将糖果装入盒子中

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

分数: 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