Phoenix and Berries
Contest: Codeforces Round 638 (Div. 2)
Difficulty rating: 2400
Tags: brute force, dp, greedy, math

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 format:
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 format:
Output one integer — the maximum number of baskets that Phoenix can fill completely.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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.

Example input:
2 4
5 2
2 1

Example output:
2

Example input:
1 5
2 3

Example output:
1

Editorial:
Solution 1:
There is no obvious greedy solution, so we will try dynamic programming. Let $$$dp[i][j]$$$ be a boolean array that denotes whether we can have $$$j$$$ extra red berries after considering the first $$$i$$$ shrubs. A berry is extra if it is not placed into a full basket (of any kind). Note that if we know that there are $$$j$$$ extra red berries, we can also easily calculate how many extra blue berries there are. Note that we can choose to never have more than $$$k-1$$$ extra red berries, because otherwise we can fill some number of baskets with them.
To transition from shrub $$$i-1$$$ to shrub $$$i$$$, we loop over all possible values $$$l$$$ from $$$0$$$ to $$$min(k-1, a_i)$$$ and check whether or not we can leave $$$l$$$ extra red berries from the current shrub $$$i$$$. For some $$$i$$$ and $$$j$$$, we can leave $$$l$$$ extra red berries and put the remaining red berries in baskets possibly with blue berries from the same shrub if $$$(a_i-l)$$$ $$$mod$$$ $$$k+b_i \ge k$$$. The reasoning for this is as follows:
First of all, we are leaving $$$l$$$ red berries (or at least trying to). We show that from this shrub, there will be at most one basket containing both red and blue berries (all from this shrub). To place the remaining red berries into full baskets, the more blue berries we have the better. It is optimal to place the remaining $$$a_i-l$$$ red berries into their own separate baskets first before merging with the blue berries (this way requires fewest blue berries to satisfy the condition). Then, if $$$(a_i-l)$$$ $$$mod$$$ $$$k+b_i$$$ is at least $$$k$$$, we can fill some basket with the remaining red berries and possibly some blue berries. Remember that we do not care about how many extra blue berries we leave because that is uniquely determined by the number of extra red berries.
Also note that we can always leave $$$a_i$$$ $$$mod$$$ $$$k$$$ extra red berries.
Denote the total number of berries as $$$t$$$. The answer will be maximum over all $$$(t-j)/k$$$ such that $$$dp[n][j]$$$ is true, $$$0\le j\le k-1$$$.
Time Complexity: $$$O(nk^2)$$$
Solution 2:
We use dynamic programming. Let $$$dp[i][j]$$$ be true if after considering the first $$$i$$$ shrubs , $$$j$$$ is the number of red berries in heterogenous baskets modulo $$$k$$$. Heterogenous baskets contain berries from the same shrub, and homogenous baskets contain berries of the same type.
Suppose we know the number of red berries in heterogeneous baskets modulo $$$k$$$. This determines the number of blue berries in heterogeneous baskets modulo $$$k$$$. Since the number of red berries in homogeneous baskets is a multiple of $$$k$$$, it also determines the number of red berries not in any baskets (we can safely assume this to be less than $$$k$$$ since otherwise we can form another basket). Similarly, we can determine the number of blue berries not in any basket, and thus deduce the number of baskets.
To compute the possible numbers of red berries in heterogeneous baskets modulo $$$k$$$, it suffices to look at each shrub separately and determine the possible numbers of red berries modulo $$$k$$$ in heterogeneous baskets for that shrub. If there is more than one heterogeneous basket for one shrub, we can rearrange the berries to leave at most one heterogeneous. Now we have two cases. If there are no heterogeneous baskets, the number of red berries in those baskets is obviously zero. If there is one heterogeneous basket, let $$$x$$$ be the number of red berries in it and $$$k-x$$$ be the number of blue berries in it. Clearly, $$$0\le x \le a_i$$$ and $$$0 \le k-x \le b_i$$$. Rearranging, we get $$$max(0,k−b_i)\le x \le min(a_i,k)$$$. These correspond to the transitions for our DP.
There exists faster solutions (like $$$O(nk)$$$), can you find it?