Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Phoenix and Berries

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPhoenix 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.

Examples

Input

2 4 5 2 2 1

Output

2

Input

1 5 2 3

Output

1

Input

2 5 2 1 1 3

Output

0

Input

1 2 1000000000 1

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.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/03/2020 15:54:53 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|