A13395 | Phoenix and Berries

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.