CF1348E.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!

凤凰正在自家后院采摘浆果。一共有 $n$ 丛灌木，第 $i$ 丛灌木上有 $a_i$ 颗红浆果和 $b_i$ 颗蓝浆果。

每个篮子可装 $k$ 颗浆果。但凤凰规定：每个篮子中所装的浆果必须全部来自同一丛灌木，或全部为同一种颜色（红色或蓝色）。换言之，篮子中所有浆果必须满足“同丛”或“同色”（或同时满足两者）。

例如，假设有两丛灌木：第一丛有 $5$ 颗红浆果和 $2$ 颗蓝浆果，第二丛有 $2$ 颗红浆果和 $1$ 颗蓝浆果。那么凤凰可以恰好装满 $2$ 个容量为 $4$ 的篮子：

• 第一个篮子装来自第一丛的 $3$ 颗红浆果和 $1$ 颗蓝浆果；
• 第二个篮子装来自第一丛剩余的 $2$ 颗红浆果，以及来自第二丛的 $2$ 颗红浆果。

请帮助凤凰计算他最多能恰好装满多少个篮子！

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.

第一行包含两个整数 $n$ 和 $k$（$1\le n, k \le 500$），分别表示灌木丛的数量和篮子的容量。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$0 \le a_i, b_i \le 10^9$），分别表示第 $i$ 棵灌木丛中红莓和蓝莓的数量。

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

输出一个整数——Phoenix 最多能完全装满的篮子数量。

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.

第一个示例已在上文描述。

在第二个示例中，凤凰可以利用第一株（也是唯一一株）灌木上的全部浆果，将一个篮子装满。

在第三个示例中，凤凰无法完全装满任何一个篮子，因为每株灌木的浆果数量均少于 $5$ 颗，红色浆果总数少于 $5$ 颗，蓝色浆果总数也少于 $5$ 颗。

在第四个示例中，凤凰可以将所有红色浆果放入篮子中，剩余一颗蓝色浆果未被放入。