まず、ナイーブな DP を考えてみましょう。
カード \(i\) を裏返すと見えている数の和が \(B_i - A_i\)増加します。この値が重要なので、以下では \( C = (B_1 - A_1, B_2 - A_2, \dots, B_N - A_N)\) として \(C\) を計算に利用していきます。

\(S_A = \sum_{i=1}^N A_i\) とします。次の Python 風のコードで表せる DP を実装すれば正しい答えを得られます。

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])

上記の内容は \(\mathrm{O}(M)\) の遷移を \(N\) 回やっていて TLE してしまうので、この DP をどうにか高速化できないか考えてみましょう。

以下では \(C\) に含まれる値の頻度を (値 \(x\), \(C\) に含まれる \(x\) の個数) という形式で管理した集合を \(F\) と表します。 例えば \(C=(-1,-1,3,3,3,3)\) のとき \(F=\lbrace (-1, 2), (3, 4) \rbrace\) です。

いくつかの事実を確認していきます。

\(C\) に含まれる要素の絶対値の和 \(S_c\) は \(M\) 以下である。

これは三角不等式から証明できます。すなわち、\(\vert C_i \vert = \vert B_i - A_i \vert \leq \vert B_i \vert + \vert - A_i \vert = A_i +B_i\) なので \( S_C \leq \sum_{i=1}^N (A_i + B_i) = M\)です。

\(F\) の要素数は高々は\(2 \times \mathrm{ceil}(\sqrt{M})\) である。

\(S_C\) が \(M\) で抑えられるのを利用します。\(F\) の要素数が \(2 \times \mathrm{ceil}(\sqrt{M}) + 1\) 以上である場合に \(S_C\) を最小化することを考えます。この場合 \(F\) は値の絶対値が小さい方から順に \(2 \times \mathrm{ceil}(\sqrt{M}) + 1\) 個入っているのが最適で、\(F = \lbrace(0,(任意)), (1,1),( -1,1),(2,1),\dots,(\mathrm{ceil}(\sqrt{M}), 1) ,(-\mathrm{ceil}(\sqrt{M}), 1) \rbrace\) です。しかしこのときの \(S_C\) は

\[ \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} \]

となり \(M\) より大きいので矛盾します。よって \(\vert F \vert\) は \(2 \times \mathrm{ceil}(\sqrt{M})\) 以下です。

上の事実を DP の高速化に利用してみましょう。DP で \(c\) が同じ場合をまとめて遷移することができれば、ナイーブな DP で \(N\) 回遷移した部分を \(\vert F \vert = \mathrm{O}(\sqrt{M})\) 回に減らすことができて、この問題を高速に解くことができそうです。
ここからはいくつかの解法がありますが、ここではデータ構造を用いない解法を説明します。

ここで突然ですが、自然数 \(n\) を次のように分割する話を考えてみます。

自然数 \(n\) が与えられる。以下のコードで表せる操作によって整数の多重集合 \(S_n\) を作ることを考える。

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

たとえば \(n=17\) のとき \(S_n = \lbrace 1, 2, 4, 8, 2 \rbrace\) である。

このとき、\(0\) 以上 \(n\) 以下のすべての自然数 \(m\) は \(S_n\) の部分和として表せる。

(証明) 最後に追加した要素を \(x\) とします。
\(x\) 以外の要素は \(2\) べきを昇順に並べたものなので 、\(n - x\) 以下の要素は 互いに異なる \(2\) べきの和として表せば \(S_n \setminus \lbrace x \rbrace\) の部分和として表せます。

また、2 進数の性質から \(n - x + 1 \geq x \iff n-2x+1 \geq 0\) が成り立つことが証明できるので、\(n-x\) より大きい要素 \(m\) については

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

が成り立つことから \(m-x\) は \(0\) 以上 \(n-x\) 以下の範囲に収まるので、\(m-x\) を \(S_n \setminus \lbrace x \rbrace\) の部分和で表して \(x\) を加えればよいです。

このような自然数の分割は DP の高速化に利用できます。
\(C\) に \(i\) が \(n\) 個含まれているとします。これを \(S_n\) の各要素 \(s_1, s_2, \dots, s_k\) について分割して 「\(i\) が \(s_1\) 個」「\(i\) が \(s_2\) 個」\(\dots\)「\(i\) が \(s_k\) 個」という \(k\) 個の部分に分けて考えます。
このとき、先に示した事実から、「\(i\) を \(x\) 個選ぶ」という操作は、上で挙げた \(k\) 個の部分からいくつかの部分を選ぶ操作に言い換えられます。
よって、各部分ごとに遷移を行う DP はすべての選び方を網羅しており、正しい答えを求められることが確認できます。Python 風のコードに直すと次の通りです。

dp = [inf] * (M + 1)
dp[S_A] = 0
for c, m in F:  # c が m 個ある
  S = partition(m) # 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])

計算量を考えます。ただちに確認できる上界として \(\mathrm{O}(M^{1.5} \log M)\) がありますが、実はもっと厳しく評価できます。

簡単のため \(\min(C) \gt 0\) の場合を考えます。(一般の場合も同じオーダーになります。)
\(\vert F \vert = k\) とします。また、\(F\) の要素が \((c_1, m_1), (c_2, m_2), \dots, (c_k, m_k)\) と表せるとします。(ここで \(c_1 \lt c_2 \lt \dots \lt c_k\) とします。)

上の DP の一番内部の for 文は各 \((c_i, m_i)\) について \(\lfloor \log_2 m_i \rfloor + 1\) 回だけ回ります。よって \(\lfloor \log_2 m_i \rfloor + 1\) の総和に \(M\) を掛けたものは計算量のオーダーと一致します。
ここで \(F\) の要素数の証明を振り返ると、\(m_i \geq 1\) であるような \(i\) の個数は \(\mathrm{O}(\sqrt{M})\) 個である事実の導出をしていました。同様の議論を行うと、\(m_i \geq 2^t\) である \(i\) の個数は \(\mathrm{O}(\sqrt{M / 2^t})\) 個であることが示せます。よって

\[\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})\]

であると言えます。以上より、上記の DP を実装すればこの問題を入力を含めて \(\mathrm{O}(N + M^{1.5})\) で計算できることが証明できました。これは十分高速に動作します。

別解としてスライド最小値や SWAG などのデータ構造を用いて DP を行う解法もあり、データ構造に詳しい人はこちらの方が簡単だと思います。詳細は略しますが、この解法も計算量 \(\mathrm{O}(N + M^{1.5})\) で解くことができます。

なお、この問題で紹介した解法は 個数制限付きナップサック問題 で利用されるアルゴリズムの 1 つです。想定解と同様の考察を経れば、個数制限付きナップサック問題を 01 ナップサック問題に帰着させることができます。

参考資料：CodeForces の記事 その1 その2

• 実装例(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)