First, let us consider a naive DP (Dynamic Programming).
Flipping card \(i\) increases the sum of visible cards by \(B_i - A_i\). We denote this important value by \( C = (B_1 - A_1, B_2 - A_2, \dots, B_N - A_N)\) and use \(C\) for derivation.

Let \(S_A = \sum_{i=1}^N A_i\). Then you get the correct answer by implementing the DP expressed by the following Python-ish code:

dp = [inf] * (M + 1)
dp[S_A] = 0
for c in C:
  nxt = copy.copy(dp)
  for i in range(M + 1):
    if 0 <= i + c <= M:
      nxt[i + c] = min(nxt[i + c], dp[i] + 1)
  dp = nxt
for i in range(M + 1):
  print(dp[i])

The algorithm above performs an \(\mathrm{O}(M)\) transition \(N\) times, which will lead to TLE (Time Limit Exceeded), so let us consider how to speed it up.

Let \(F\) be a set that contains the frequency of values in \(C\) in the format (value \(x\), the number of \(x\)’s in \(C\)). For example, if \(C=(-1,-1,3,3,3,3)\), we have \(F=\lbrace (-1, 2), (3, 4) \rbrace\).

Here are some facts:

• The sum \(S_c\) of absolute values in \(C\) is at most \(M\).

This can be proved by the triangle inequality. That is, \(\vert C_i \vert = \vert B_i - A_i \vert \leq \vert B_i \vert + \vert - A_i \vert = A_i +B_i\), so \( S_C \leq \sum_{i=1}^N (A_i + B_i) = M\).

\(F\) has at most \(2 \times \mathrm{ceil}(\sqrt{M})\) elements.

We can use the fact that \(S_C\) is bounded by \(M\). Consider minimizing \(S_C\) when \(F\) has at least \((2 \times \mathrm{ceil}(\sqrt{M}) + 1)\) elements. Then it is optimal that \(F\) contains \((2 \times \mathrm{ceil}(\sqrt{M}) + 1)\) values with the smallest absolute values, so \(F = \lbrace(0,(\text{arbitrary})), (1,1),( -1,1),(2,1),\dots,(\mathrm{ceil}(\sqrt{M}), 1) ,(-\mathrm{ceil}(\sqrt{M}), 1) \rbrace\). However,

\[ \begin{aligned} S_C &\geq 0 + 2 \times(1 + 2 + \dots + \mathrm{ceil}(\sqrt{M})) \\ &\geq 2 \times \frac{\sqrt{M}(\sqrt{M} + 1)}{2} \\ &= M + \sqrt{M} \\ &\gt M, \end{aligned} \]

which is a contradiction. Therefore \(\vert F \vert\) is at most \(2 \times \mathrm{ceil}(\sqrt{M})\).

How can we use the fact to optimize the DP? If we can make a transition of the DP for the same \(c\) at once, then we can reduce \(N\) transitions in the naive DP to \(\vert F \vert = \mathrm{O}(\sqrt{M})\) transitions, thus solving this problem fast.
Now there are several approaches; we introduce a solution that does not require a data structure.

It is a bit sudden, but let us consider dividing a natural number \(n\) as follows.

Given a natural number \(n\), consider constructing a multiset of integers \(S_n\) by the operations represented by the following code:

S_n = []
x = 1
while n:
  s = min(x, n)
  S_n.append(s)
  n -= s
  x *= 2

For example, if \(n=17\), we have \(S_n = \lbrace 1, 2, 4, 8, 2 \rbrace\).

Then, every integer between \(0\) and \(n\) (inclusive) can be expressed as a partial sum of \(S_n\).

(Proof) Let \(x\) be the last element added.
The elements other than \(x\) forms an ascending sequence of powers of \(2\), so every elements at most \(n - x\) (inclusive) can be expressed as powers of two, and thus a partial sum of \(S_n \setminus \lbrace x \rbrace\).

Also, we can prove the property of binaries that \(n - x + 1 \geq x \iff n-2x+1 \geq 0\), so for integers \(m\) greater than \(n-x\),

\[0 \leq (n-x+1) - x \leq m-x \leq n-x,\]

so \(n-x\) is in the range of \(0\) and \(n-x\); thus we can express \(n-x\) as a partial sum of \(S_n \setminus \lbrace x \rbrace\) and then add \(x\).

Such a division of integer can speed up the DP.
Suppose \(C\) has \(n\) \(i\)’s. Divide this into \(k\) parts, “\(s_1\) \(i\)’s”, “\(S_2\) \(i\)’s”, \(\dots\), and \(s_k\) \(i\)’s” corresponding to each element \(s_1, s_2, \dots, s_k\) of \(S_n\).
Then, by the fact above, “choosing \(x\) \(i\)’s” is boiled down to choosing some of the \(k\) parts we listed.
Therefore, we can check that the DP in which a transition is done for each of the parts covers all the combination, and that it yields the correct answer. In a Python-ish code, it will be like:

dp = [inf] * (M + 1)
dp[S_A] = 0
for c, m in F:  # there are m c's
  S = partition(m) # multiset that is a division of m
  for s in S:
    nxt = copy.copy(dp)
    for i in range(M + 1):
      if 0 <= i + c * s <= M:
        nxt[i + c * s] = min(nxt[i + c * s], dp[i] + s)
    dp = nxt
for i in range(M + 1):
  print(dp[i])

Let us evaluate the complexity. One obvious upper bound is \(\mathrm{O}(M^{1.5} \log M)\), but it can be evaluated even stricter.

For simplicity, we consider \(\min(C) \gt 0\). (The general case yield the same order.)
Let \(\vert F \vert = k\). Also, let \((c_1, m_1), (c_2, m_2), \dots, (c_k, m_k)\) be the elements of \(F\) (where \(c_1 \lt c_2 \lt \dots \lt c_k\)).

The innermost for statement in the DP above is iterated exactly \(\lfloor \log_2 m_i \rfloor + 1\) times for each \((c_i, m_i)\), so \(M\) multiplied by the sum of \(\lfloor \log_2 m_i \rfloor + 1\) equals the order of the complexity.
Now let us look back the proof on the number of elements of \(F\); we have shown that the number of \(i\)’s such that \(m_i \geq 1\) is \(\mathrm{O}(\sqrt{M})\). Similarly, we can show that there are \(\mathrm{O}(\sqrt{M / 2^t})\) number of \(i\)’s such that \(m_i \geq 2^t\). Therefore we can say that

\[\sum_{i=1}^k (\lfloor \log_2 m_i \rfloor + 1) = \mathrm{O}\left( \sum_{t=0}^{\infty} \sqrt{\frac{M}{2^t}}\right) = \mathrm{O}(\sqrt{M}).\]

Hence we have proved that this problem can be solved as fast as \(\mathrm{O}(N + M^{1.5})\) including input and output by implementing the DP above, which is fast enough.

Alternatively, we may do DP with “sliding minimum” trick or a data structure like SWAG, with which those who are familiar with data structure may be familiar. We omit the details, but this can also be solved in a total of \(\mathrm{O}(N + M^{1.5})\) time, too.

By the way, the solution we introduced in this problem is one of the algorithms that is used for Knapsack problem with number limits. With the same observations as the intended solution, the Knapsack problem with number limits can be solved by boiling down to a 01 Knapsack problem.

Reference: article in CodeForces #1 #2

• Sample code (PyPy)

from collections import defaultdict
N, M = map(int, input().split())
S_A = 0
F = defaultdict(int)
for i in range(N):
  A, B = map(int, input().split())
  S_A += A
  F[B - A] += 1
dp = [10**9] * (M + 1)
dp[S_A] = 0
for c, m in F.items():
  if c == 0:
    continue
  x = 1
  while m:
    s = min(x, m)
    if c > 0:
      for i in reversed(range(M - c * s + 1)):
        dp[i + c * s] = min(dp[i + c * s], dp[i] + s)
    else:
      for i in range(-c * s, M + 1):
        dp[i + c * s] = min(dp[i + c * s], dp[i] + s)
    m -= s
    x *= 2
for i in range(M + 1):
  print(dp[i] if dp[i] <= N else -1)