Nayra đang tham dự một lễ hội và chơi một trò chơi mà giải thưởng lớn là một chuyến du lịch đến Laguna Colorada. Trò chơi gồm việc dùng các đồng xu (token) để mua các phiếu thưởng (coupon). Việc mua một phiếu thưởng có thể đem lại thêm xu. Mục tiêu là thu được càng nhiều phiếu thưởng càng tốt.

Cô bắt đầu trò chơi với \(A\) đồng xu. Có \(N\) phiếu thưởng, được đánh số từ \(0\) đến \(N-1\). Để mua phiếu thưởng \(i\) (\(0 \le i < N\)), Nayra phải trả \(P[i]\) đồng xu (và cô phải có ít nhất \(P[i]\) đồng xu trước khi mua). Mỗi phiếu thưởng chỉ có thể được mua tối đa một lần.

Hơn nữa, mỗi phiếu thưởng \(i\) (\(0 \le i < N\)) được gán một loại, ký hiệu là \(T[i]\), là một số nguyên từ \(1\) đến \(4\). Sau khi Nayra mua phiếu thưởng \(i\), số đồng xu còn lại của cô sẽ được nhân với \(T[i]\). Cụ thể, nếu tại một thời điểm nào đó trong trò chơi cô có \(X\) đồng xu và mua phiếu thưởng \(i\) (yêu cầu \(X \ge P[i]\)), thì sau khi mua cô sẽ có \((X - P[i]) \cdot T[i]\) đồng xu.

Nhiệm vụ của bạn là xác định Nayra nên mua những phiếu thưởng nào và theo thứ tự ra sao, để tối đa hóa tổng số phiếu thưởng cô có được vào cuối trò chơi. Nếu có nhiều hơn một dãy mua đạt được kết quả tối đa, bạn có thể đưa ra một dãy bất kỳ trong số đó.

Chi tiết cài đặt

Bạn cần cài đặt thủ tục sau, được khai báo trong festival.h:

std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T)

• \(A\): số đồng xu ban đầu của Nayra.
• \(P\): mảng độ dài \(N\) chứa giá của các phiếu thưởng.
• \(T\): mảng độ dài \(N\) chứa loại của các phiếu thưởng.
• Thủ tục này được gọi đúng một lần cho mỗi test case.

Thủ tục cần trả về một mảng \(R\), mô tả các phiếu thưởng mà Nayra mua như sau:

• Độ dài của \(R\) phải bằng số phiếu thưởng tối đa mà cô có thể mua.
• Các phần tử của mảng là chỉ số của các phiếu thưởng cô nên mua, theo thứ tự thời gian. Nghĩa là, cô mua phiếu thưởng \(R[0]\) đầu tiên, sau đó là \(R[1]\), và cứ thế tiếp tục.
• Tất cả các phần tử của \(R\) phải khác nhau.

Nếu không thể mua được phiếu thưởng nào, \(R\) phải là một mảng rỗng.

Ràng buộc

• \(1 \le N \le 200\,000\)
• \(1 \le A \le 10^9\)
• \(1 \le P[i] \le 10^9\) với mọi \(i\) thỏa \(0 \le i < N\).
• \(1 \le T[i] \le 4\) với mọi \(i\) thỏa \(0 \le i < N\).

Phân nhóm

• Subtask 1 (5 điểm): \(T[i] = 1\) với mọi \(i\) thỏa \(0 \le i < N\).
• Subtask 2 (7 điểm): \(N \le 3000\); \(T[i] \le 2\) với mọi \(i\) thỏa \(0 \le i < N\).
• Subtask 3 (12 điểm): \(T[i] \le 2\) với mọi \(i\) thỏa \(0 \le i < N\).
• Subtask 4 (15 điểm): \(N \le 70\).
• Subtask 5 (27 điểm): Nayra có thể mua tất cả \(N\) phiếu thưởng (theo một thứ tự nào đó).
• Subtask 6 (16 điểm): \((A - P[i]) \cdot T[i] < A\) với mọi \(i\) thỏa \(0 \le i < N\).
• Subtask 7 (18 điểm): Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1. Xét lời gọi sau:

max_coupons(13, [4, 500, 8, 14], [1, 3, 3, 4])

Ban đầu Nayra có \(A = 13\) đồng xu. Cô có thể mua \(3\) phiếu thưởng theo thứ tự sau:

Trong ví dụ này, Nayra không thể mua nhiều hơn \(3\) phiếu thưởng, và dãy mua được mô tả ở trên là cách duy nhất để cô mua được \(3\) phiếu. Do đó, thủ tục cần trả về \([2, 3, 0]\).

Ví dụ 2. Xét lời gọi sau:

max_coupons(9, [6, 5], [2, 3])

Trong ví dụ này, Nayra có thể mua cả hai phiếu thưởng theo thứ tự bất kỳ. Do đó, thủ tục cần trả về hoặc \([0, 1]\) hoặc \([1, 0]\).

Ví dụ 3. Xét lời gọi sau:

max_coupons(1, [2, 5, 7], [4, 3, 1])

Trong ví dụ này, Nayra chỉ có một đồng xu, không đủ để mua bất kỳ phiếu thưởng nào. Do đó, thủ tục cần trả về \([\,]\) (một mảng rỗng).

Chương trình chấm mẫu

Định dạng đầu vào:

N A
P[0] T[0]
P[1] T[1]
...
P[N-1] T[N-1]

Định dạng đầu ra:

S
R[0] R[1] ... R[S-1]

Ở đây, \(S\) là độ dài của mảng \(R\) được trả về bởi max_coupons.

4 13
4 1
500 3
8 3
14 4

3
2 3 0

2 9
6 2
5 3

2
0 1

3 1
2 4
5 3
7 1

0