Marvin the Martian đang đóng gói một chiếc balo. Trước mặt anh ta có $n$ vật phẩm, được đánh số từ $1$ đến $n$. Mỗi vật phẩm có hai đặc tính: vật phẩm thứ $i$ có độ kỳ lạ $w_i$ và chi phí $c_i$. Độ kỳ lạ của một vật phẩm là một số nguyên không âm có biểu diễn nhị phân chứa tối đa $k$ bit ($0 \le w_i < 2^k$), và chi phí của một vật phẩm là một số nguyên không âm không vượt quá $10^9$ ($0 \le c_i \le 10^9$).
Tổng chi phí của một tập vật phẩm là tổng các chi phí của các vật phẩm trong tập đó, và tổng độ kỳ lạ của tập này được định nghĩa là phép OR theo bit của các độ kỳ lạ của các vật phẩm trong tập đó.
Marvin gọi một tập vật phẩm là có giá trị nếu tổng chi phí của nó ít nhất là $C$. Với mỗi $i$ từ $1$ đến $n$, Marvin muốn chọn một tập vật phẩm có giá trị từ các vật phẩm có chỉ số không vượt quá $i$ sao cho tổng độ kỳ lạ của nó là nhỏ nhất có thể.
Phép OR theo bit của một tập hợp các số nguyên được định nghĩa như sau: xét biểu diễn nhị phân của các số này. Khi đó bit thứ $i$ của kết quả là $1$ nếu bit thứ $i$ của ít nhất một trong các số trong tập hợp là $1$. Trong các ngôn ngữ lập trình, phép toán này được ký hiệu bởi ký tự "|". Ví dụ, $(10 \mid 3 \mid 9) = (1010_2 \mid 0011_2 \mid 1001_2) = 1011_2 = 11$.
Dữ liệu vào
Dòng đầu tiên chứa ba số nguyên $n$, $k$ và $C$ ($1 \le n \le 2\,000\,000$, $1 \le k \le 22$, $1 \le C \le 10^{15}$) — số lượng vật phẩm, giới hạn về số bit trong biểu diễn nhị phân của độ kỳ lạ, và chi phí tối thiểu của một tập con có giá trị.
Mỗi dòng trong số $n$ dòng tiếp theo chứa hai số nguyên $w_i$ và $c_i$ ($0 \le w_i < 2^k$, $0 \le c_i \le 10^9$) — độ kỳ lạ và chi phí của vật phẩm tương ứng.
Dữ liệu ra
In ra $n$ số nguyên, trong đó số nguyên thứ $i$ phải bằng tổng độ kỳ lạ nhỏ nhất của một tập con có giá trị gồm $i$ vật phẩm đầu tiên. Nếu không thể chọn được tập con có giá trị, in ra $-1$.
Nhiệm vụ con
| Nhiệm vụ con | Điểm | $n$ | $k$ | Ràng buộc bổ sung | Nhiệm vụ con bắt buộc |
|---|---|---|---|---|---|
| 1 | 10 | $n \le 20$ | $k \le 10$ | Samples | |
| 2 | 11 | $n \le 100$ | $k \le 10$ | Samples, 1 | |
| 3 | 14 | $n \le 50\,000$ | $k \le 10$ | Samples, 1–2 | |
| 4 | 13 | $n \le 1\,000\,000$ | $k \le 19$ | All $w_i$ are powers of two | |
| 5 | 11 | $n \le 2\,000$ | Samples, 1–2 | ||
| 6 | 18 | $n \le 500\,000$ | $k \le 16$ | Samples, 1–3 | |
| 7 | 6 | $n \le 1\,000\,000$ | $k \le 19$ | Samples, 1–4, 6 | |
| 8 | 6 | $k \le 19$ | Samples, 1–4, 6–7 | ||
| 9 | 11 | Samples, 1–8 |
Ví dụ
Đầu vào 1
5 4 12 8 7 2 6 3 6 1 12 3 5
Đầu ra 1
-1 10 3 1 1
Ghi chú
Với $i = 1$, có một vật phẩm với độ kỳ lạ $8$ và chi phí $7$. Vì không thể chọn một tập con của một vật phẩm sao cho tổng chi phí ít nhất là $12$, câu trả lời là $-1$.
Với $i = 2$, có hai vật phẩm, và cách duy nhất để chọn một tập con có giá trị là lấy cả hai vật phẩm. Tổng độ kỳ lạ sẽ là $8 \mid 2 = 10$.
Với $i = 3$, bất kỳ tập con nào gồm hai hoặc nhiều vật phẩm đều có giá trị. Lựa chọn tối ưu là chọn vật phẩm thứ hai và thứ ba, và tổng độ kỳ lạ của chúng là $2 \mid 3 = 3$.
Với $i = 4$, có thể chọn chỉ riêng vật phẩm thứ tư, có chi phí đủ, và độ kỳ lạ của nó là $1$, là giá trị nhỏ nhất có thể. Với $i = 5$, cũng tối ưu khi chỉ chọn vật phẩm thứ tư.