JOI-kun mua \(N\) chiếc bánh, được đánh số từ \(1\) đến \(N\). Bánh \(i\) có kích thước \(A_i\). Kế hoạch thứ \(i\) là đặt lên bánh \(i\) một quả dâu có độ ngọt \(V_i\).

Hãy chọn thực hiện không hoặc nhiều kế hoạch sao cho với mọi hai bánh khác nhau đã được đặt dâu:

• tổng kích thước của chúng không bằng \(S\);
• hiệu tuyệt đối giữa kích thước của chúng không bằng \(D\).

Tìm tổng độ ngọt lớn nhất có thể. Nếu không chọn kế hoạch nào, tổng độ ngọt bằng \(0\).

Dữ liệu vào

Dòng đầu gồm \(N,S,D\). Dòng thứ hai gồm \(A_1,A_2,\ldots,A_N\). Dòng thứ ba gồm \(V_1,V_2,\ldots,V_N\).

Dữ liệu ra

In tổng độ ngọt lớn nhất có thể.

Ràng buộc

• \(1\le N\le200000\).
• \(1\le S,D,A_i,V_i\le10^9\).
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

1. \(7\) điểm: \(N\le20\).
2. \(14\) điểm: \(S\le40\), \(D\le20\), \(A_i\le20\).
3. \(18\) điểm: \(S=1\).
4. \(30\) điểm: \(D=1\) và \(S\) lẻ.
5. \(15\) điểm: \(D=1\).
6. \(16\) điểm: không có ràng buộc thêm.

Ví dụ

5 8 3
3 4 5 6 7
10 6 7 5 4

18

3 1 3
4 7 10
3 10 8

11

10 1 1
1 2 3 4 5 6 7 8 9 10
3 1 4 1 5 9 2 6 5 3

25

Nguồn

JOIG 2025/2026 - Chung kết, Cuộc thi 1, bài Cake 4.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.