AT_abc269_g [ABC269G] Reversible Cards 2

题目描述

有 $N$ 张编号为 $1$ 到 $N$ 的卡片。
卡片 $i$ 的正面写有整数 $A_i$，反面写有整数 $B_i$。并且有 $\sum_{i=1}^N (A_i + B_i) = M$。
对于 $k=0,1,2,\ldots,M$，请解决以下问题：

$N$ 张卡片全部正面朝上排列。你可以选择 $0$ 张到 $N$ 张卡片，将它们翻面。
使得可见数字之和为 $k$，最少需要翻面多少张卡片？请输出所需的最小张数。
如果无论如何翻面都无法使可见数字之和为 $k$，请输出 $-1$。

输入格式

输入以以下格式从标准输入给出。

$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出格式

请输出 $M+1$ 行。第 $i$ 行输出当 $k=i-1$ 时的答案。

输入输出样例 #1

输入 #1

3 6
0 2
1 0
0 3

输出 #1

1
0
2
1
1
3
2

输入输出样例 #2

输入 #2

2 3
1 1
0 1

输出 #2

-1
0
1
-1

输入输出样例 #3

输入 #3

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

输出 #3

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

说明/提示

限制条件

• $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$
• 所有输入值均为整数

样例解释 1

例如，当 $k=0$ 时，只需将第 $2$ 张卡片翻面，就能使可见数字之和为 $0+0+0=0$，这是最优解。
又如，当 $k=5$ 时，将所有卡片翻面，可见数字之和为 $2+0+3=5$，这是最优解。

由 ChatGPT 4.1 翻译