A - Packing Sweets into Boxes Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君と青木君は、文化祭の模擬店で N 種類のお菓子を販売するために準備をしています。

i 番目の種類のお菓子について、高橋君が A_i 個、青木君が B_i 個を持ち寄りました。同じ種類のお菓子であれば、高橋君のものと青木君のものに区別はなく、合わせて A_i + B_i 個として扱います。

これらのお菓子をすべて箱に詰めて販売ブースへ運びます。

箱は必要なだけいくつでも用意できます。1 つの箱にはお菓子を 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-bit 符号付き整数に収まる

入力

入力は以下の形式で与えられる。

N K
A_1 B_1
A_2 B_2
\vdots
A_N B_N

1 行目には、お菓子の種類数 N と、1 箱あたりに入れられるお菓子の最大個数 K がスペース区切りで与えられる。

続く N 行のうち i 行目には、i 番目の種類について高橋君が用意した個数 A_i と青木君が用意した個数 B_i がスペース区切りで与えられる。

出力

すべてのお菓子を運ぶために必要な箱の数の最小値を 1 行で出力してください。

入力例 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

Score : 233 pts

Problem Statement

Takahashi and Aoki are preparing to sell N types of sweets at their booth for the school cultural festival.

For the i-th type of sweet, Takahashi brought A_i pieces and Aoki brought B_i pieces. Sweets of the same type are indistinguishable regardless of who brought them, so they are treated as a combined total of A_i + B_i pieces.

All of these sweets must be packed into boxes and carried to the sales booth.

As many boxes as needed are available. Each box can hold between 1 and K sweets (inclusive), but sweets of different types cannot be placed in the same box.

If the total number of sweets of a certain type is 0, no boxes need to be used for that type.

Find the minimum number of boxes required to pack all the sweets with none left over.

Constraints

  • 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
  • All input values are integers
  • Under these constraints, the answer fits in a 64-bit signed integer

Input

The input is given in the following format.

N K
A_1 B_1
A_2 B_2
\vdots
A_N B_N

The first line contains the number of types of sweets N and the maximum number of sweets per box K, separated by a space.

Each of the following N lines contains, for the i-th type, the number of pieces A_i prepared by Takahashi and the number of pieces B_i prepared by Aoki, separated by a space.

Output

Print the minimum number of boxes required to carry all the sweets, on a single line.

Sample Input 1

3 5
1 2
4 0
3 5

Sample Output 1

4

Sample Input 2

4 3
0 0
1 2
3 0
2 5

Sample Output 2

5

Sample Input 3

8 7
2 3
7 0
6 6
0 5
14 1
8 13
0 0
20 4

Sample Output 3

15

Sample Input 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

Sample Output 4

558598835

Sample Input 5

1 1000000000
0 0

Sample Output 5

0