#5759. 「ROI 2026 Day2」火星背包

标签: 传统 | 时间限制: 1000 ms | 内存限制: 1024 MiB |

题目描述

译自 ROI 2026 Day2 T3. Марсианский рюкзак

火星人 Marvin 正在整理他的背包。在他面前摆放着 $n$ 个物品，编号从 $1$ 到 $n$。每个物品都有两个属性：第 $i$ 个物品的奇怪值 $w_i$ 和价值 $c_i$。奇怪值是一个非负整数，其二进制表示中包含不超过 $k$ 个比特位 $(0 \le w_i < 2^k)$；价值是一个非负整数，不超过 $10^9$ $(0 \le c_i \le 10^9)$。

一个物品集合的总价值等于其中所有物品价值之和，而该集合的总奇怪值定义为其中所有物品奇怪值的按位或 (OR) 运算结果。

如果一个物品集合的总价值不小于 $C$，Marvin 就称其为有价值的。对于从 $1$ 到 $n$ 的每个 $i$，Marvin 都希望从编号不超过 $i$ 的物品中选出一个有价值的集合，使得其总奇怪值尽可能小。

一组整数的按位或运算定义如下：考虑这些数字的二进制表示，如果集合中至少有一个数字在第 $j$ 位上为 $1$，则结果的第 $j$ 位也为 $1$。在编程语言中，此运算通常用符号 $\mid$ 表示。例如，$(10 \mid 3 \mid 9) = (1010_2 \mid 0011_2 \mid 1001_2) = 1011_2 = 11$。

输入格式

第一行包含三个整数 $n, k$ 和 $C$ $(1 \le n \le 2\,000\,000, 1 \le k \le 22, 1 \le C \le 10^{15})$，分别代表物品的数量、奇怪值二进制表示的位数限制以及有价值集合的最小价值要求。

接下来的 $n$ 行，每行包含两个整数 $w_i$ 和 $c_i$ $(0 \le w_i < 2^k, 0 \le c_i \le 10^9)$，分别代表对应物品的奇怪值和价值。

输出格式

输出 $n$ 个整数，其中第 $i$ 个整数应等于前 $i$ 个物品所能组成的有价值集合的最小总奇怪值。若无法选出有价值的集合，则输出 $-1$。

样例

输入

5 4 12
8 7
2 6
3 6
1 12
3 5

输出

-1
10
3
1
1

对于 $i = 1$，只有一个奇怪值为 $8$ 且价值为 $7$ 的物品。由于无法选出一个物品子集使得其价值总和至少为 $12$，因此答案为 $-1$。

对于 $i = 2$，有两个物品。要选出有价值的子集，唯一的方案是同时选取这两个物品。总奇怪值等于 $8 \mid 2 = 10$。

对于 $i = 3$，任何包含两个或更多物品的子集都是有价值的。最优方案是选择第二个和第三个物品，它们的总奇怪值为 $2 \mid 3 = 3$。

对于 $i = 4$，只选择第四个物品变得可行，其价值足够且奇怪值为 $1$，这是可能的最小值。

对于 $i = 5$，选择第四个物品同样是最优方案。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。