Phoenix and Berries

题意翻译

小P在花园里摘红梅和蓝莓。 他一共有$n$棵树，第$i$棵树上有$a_i$个红梅和$b_i$个蓝莓。由于小P有强迫症，所以他希望一个篮子里的梅子都来自同一棵树或都是一种颜色的（或两者同时满足）。 给出篮子的最大容量 $k$，求能够被装满的篮子数量的最大值（不必用完所有梅子）

题目描述

Phoenix is picking berries in his backyard. There are $ n $ shrubs, and each shrub has $ a_i $ red berries and $ b_i $ blue berries. Each basket can contain $ k $ berries. But, Phoenix has decided that each basket may only contain berries from the same shrub or berries of the same color (red or blue). In other words, all berries in a basket must be from the same shrub or/and have the same color. For example, if there are two shrubs with $ 5 $ red and $ 2 $ blue berries in the first shrub and $ 2 $ red and $ 1 $ blue berries in the second shrub then Phoenix can fill $ 2 $ baskets of capacity $ 4 $ completely: - the first basket will contain $ 3 $ red and $ 1 $ blue berries from the first shrub; - the second basket will contain the $ 2 $ remaining red berries from the first shrub and $ 2 $ red berries from the second shrub. Help Phoenix determine the maximum number of baskets he can fill completely!

输入输出格式

输入格式

The first line contains two integers $ n $ and $ k $ ( $ 1\le n, k \le 500 $ ) — the number of shrubs and the basket capacity, respectively. The $ i $ -th of the next $ n $ lines contain two integers $ a_i $ and $ b_i $ ( $ 0 \le a_i, b_i \le 10^9 $ ) — the number of red and blue berries in the $ i $ -th shrub, respectively.

输出格式

Output one integer — the maximum number of baskets that Phoenix can fill completely.

输入输出样例

输入样例 #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

说明

The first example is described above. In the second example, Phoenix can fill one basket fully using all the berries from the first (and only) shrub. In the third example, Phoenix cannot fill any basket completely because there are less than $ 5 $ berries in each shrub, less than $ 5 $ total red berries, and less than $ 5 $ total blue berries. In the fourth example, Phoenix can put all the red berries into baskets, leaving an extra blue berry behind.