Phoenix and Berries

2000ms

262144K

Description:

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!

Input:

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:

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

Sample Input:

2 4
5 2
2 1

Sample Output:

Sample Input:

1 5
2 3

Sample Output:

Sample Input:

2 5
2 1
1 3

Sample Output:

Sample Input:

1 2
1000000000 1

Sample Output:

500000000

Note:

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.

Informação

Provedor Codeforces

Código CF1348E