CF1348E Phoenix and Berries

Phoenix 正在自家后院采摘浆果。有 $n$ 棵灌木，每棵灌木上有 $a_i$ 个红色浆果和 $b_i$ 个蓝色浆果。 每个篮子最多可以装 $k$ 个浆果。但是，Phoenix 决定每个篮子只能装来自同一棵灌木的浆果，或者装同一种颜色（红色或蓝色）的浆果。换句话说，一个篮子里的所有浆果必须来自同一棵灌木，或/和具有相同的颜色。 例如，如果有两棵灌木，第一棵有 $5$ 个红色和 $2$ 个蓝色浆果，第二棵有 $2$ 个红色和 $1$ 个蓝色浆果，那么 Phoenix 可以完全装满 $2$ 个容量为 $4$ 的篮子： - 第一个篮子可以装 $3$ 个红色和 $1$ 个蓝色浆果，全部来自第一棵灌木； - 第二个篮子可以装第一棵灌木剩下的 $2$ 个红色浆果和第二棵灌木的 $2$ 个红色浆果。 请你帮助 Phoenix 计算，他最多可以完全装满多少个篮子！

第一行包含两个整数 $n$ 和 $k$（$1 \le n, k \le 500$），分别表示灌木的数量和篮子的容量。 接下来的 $n$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$0 \le a_i, b_i \le 10^9$），分别表示第 $i$ 棵灌木上的红色和蓝色浆果数量。

输出一个整数，表示 Phoenix 最多可以完全装满多少个篮子。

第一个样例已在题目描述中给出。 第二个样例中，Phoenix 可以用第一棵（也是唯一一棵）灌木上的所有浆果装满一个篮子。 第三个样例中，Phoenix 无法完全装满任何一个篮子，因为每棵灌木上的浆果都少于 $5$ 个，所有红色浆果的总数也少于 $5$，所有蓝色浆果的总数也少于 $5$。 第四个样例中，Phoenix 可以把所有红色浆果都装进篮子，剩下一个蓝色浆果。 由 ChatGPT 4.1 翻译