P17024 [ROI 2026 Day2] Mars Knapsack

Since the testdata for this problem is much larger than 4 GB and exceeds Luogu’s judging limit, some test points in Subtask 9 were removed. Please judge at https://www.luogu.com.cn/problem/U697179. Because the testdata is large, the judge may need 2–4 minutes to load the testdata. This problem cannot provide testdata downloads. You may also test your solution at the link above first, and then submit to this problem to reduce waiting time.

The Martian Marvin is organizing his knapsack. In front of him there are $n$ items, numbered from $1$ to $n$. Each item has two attributes: item $i$ has **weirdness** $w_i$ and **value** $c_i$. Weirdness is a non-negative integer whose binary representation has at most $k$ bits ($0 \le w_i < 2^k$). Value is a non-negative integer not exceeding $10^9$ ($0 \le c_i \le 10^9$). The total value of a set of items is the sum of the values of all items in it, and the total weirdness is defined as the bitwise OR of the weirdness values of all items in it. Marvin calls a set of items **valuable** if and only if its total value is at least $C$. For each $i$ ($1 \le i \le n$), Marvin wants to choose a valuable subset from the items with indices at most $i$, so that the subset’s total weirdness is as small as possible. The bitwise OR of a set of integers is defined as follows: consider the binary representations of these numbers. The $i$-th bit of the result is $1$ if and only if at least one of these numbers has its $i$-th bit equal to $1$. In programming languages, this operation is denoted by the symbol $\mid$. For example, $(10 \mid 3 \mid 9) = (1010_2 \mid 0011_2 \mid 1001_2) = 1011_2 = 11$.

The first line contains three integers $n$, $k$, $C$ ($1 \le n \le 2\,000\,000$, $1 \le k \le 22$, $1 \le C \le 10^{15}$), representing the number of items, the upper limit on the number of bits in weirdness, and the minimum total value for a valuable subset. The next $n$ lines each contain two integers $w_i$ and $c_i$ ($0 \le w_i < 2^k$, $0 \le c_i \le 10^9$), representing the weirdness and value of item $i$.

Output $n$ numbers. The $i$-th number should be the minimum total weirdness among valuable subsets chosen from the first $i$ items. If it is impossible to choose such a subset, output $-1$.

### Explanation For $i = 1$, there is only one item with weirdness $8$ and value $7$. Since it is impossible to choose a subset whose total value is at least $12$, the answer is $-1$. For $i = 2$, there are two items. The only valuable choice is to take both items, and the total weirdness is $8 \mid 2 = 10$. For $i = 3$, any subset containing at least two items is valuable. The best plan is to choose item $2$ and item $3$, and the total weirdness is $2 \mid 3 = 3$. For $i = 4$, you can take only the fourth item, since its value is already enough. Its weirdness is $1$, which is the smallest possible value. For $i = 5$, taking only the fourth item is also optimal. ### Subtasks | Subtask | Score | $n$ | $k$ | Additional Constraints | Dependencies | |:---:|:---:|:---:|:---:|:---|:---:| | 1 | 10 | $n \le 20$ | $k \le 10$ | -- | | | 2 | 11 | $n \le 100$ | $k \le 10$ | -- | 1 | | 3 | 14 | $n \le 50\,000$ | $k \le 10$ | -- | 1–2 | | 4 | 13 | $n \le 1\,000\,000$ | $k \le 19$ | All $w_i$ are powers of $2$ | -- | | 5 | 11 | $n \le 2\,000$ | -- | -- | 1–2 | | 6 | 18 | $n \le 500\,000$ | $k \le 16$ | -- | 1–3 | | 7 | 6 | $n \le 1\,000\,000$ | $k \le 19$ | -- | 1–4, 6 | | 8 | 6 | -- | $k \le 19$ | -- | 1–4, 6–7 | | 9 | 11 | -- | -- | -- | 1–8 | Translated by DeepSeek V4 Pro. Translated by ChatGPT 5