Score : $600$ points

问题描述

我们有 $N$ 张卡片，编号为 $1$ 到 $N$。
第 $i$ 张卡片正面写有整数 $A_i$，背面写有整数 $B_i$。这里，$\sum_{i=1}^N (A_i + B_i) = M$。

对于每个 $k=0,1,2,...,M$，解决以下问题：

这 $N$ 张卡片被排列成正面朝上可见的状态。你可以选择翻转从 $0$ 到 $N$ 张（包含）任意数量的卡片。
为了使得所有可见数字之和等于 $k$，至少需要翻转多少张卡片？请输出这个卡片的数量。
如果无法通过翻转卡片使得可见数字之和等于 $k$，则输出 $-1$。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

We have $N$ cards numbered $1$ to $N$.
Card $i$ has an integer $A_i$ written on the front and an integer $B_i$ written on the back. Here, $\sum_{i=1}^N (A_i + B_i) = M$.
For each $k=0,1,2,...,M$, solve the following problem.

The $N$ cards are arranged so that their front sides are visible. You may choose between $0$ and $N$ cards (inclusive) and flip them.
To make the sum of the visible numbers equal to $k$, at least how many cards must be flipped? Print this number of cards.
If there is no way to flip cards to make the sum of the visible numbers equal to $k$, print $-1$ instead.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq 2 \times 10^5$
• $0 \leq A_i, B_i \leq M$
• $\sum_{i=1}^N (A_i + B_i) = M$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_N$ $B_N$

Output

Print $M+1$ lines. The $i$-th line should contain the answer for $k=i-1$.

Sample Input 1

3 6
0 2
1 0
0 3

Sample Output 1

1
0
2
1
1
3
2

For $k=0$, for instance, flipping just card $2$ makes the sum of the visible numbers $0+0+0=0$. This choice is optimal.
For $k=5$, flipping all cards makes the sum of the visible numbers $2+0+3=5$. This choice is optimal.

Sample Input 2

2 3
1 1
0 1

Sample Output 2

-1
0
1
-1

Sample Input 3

5 12
0 1
0 3
1 0
0 5
0 2

Sample Output 3

1
0
1
1
1
2
1
2
2
2
3
3
4

update @ 2024/3/10 11:22:14