Sau khi thi đấu xuất sắc và trở về từ kỳ thi ICPC APAC 2026 tại Đài Loan với tấm Huy Chương Đồng, Quang quyết định dạo quanh khu chợ đêm Đào Viên để mua quà lưu niệm cho các bạn trong đội tuyển.

Trong cửa hàng có \(N\) món đồ lưu niệm, món thứ \(i\) có khối lượng là \(W_i\) và mang lại lượng niềm vui (có thể đo đếm được ?!) là \(V_i\). Tiền thì không thành vấn đề, Quang dư sức mua hết cả \(N\) món đồ trong tiệm, nhưng vali của Quang chỉ có thể chứa được tổng khối lượng tối đa là \(M\).

Cửa hàng có một chương trình khuyến mãi cho những thí sinh có thành tích tốt tại ICPC APAC 2026: tặng ngay \(K\) thẻ "Nhân đôi niềm vui". Khi sử dụng một thẻ này lên một món đồ bất kỳ mà Quang mua, giá trị niềm vui \(V_i\) của món đó sẽ lập tức được tăng lên gấp đôi.

Tuy nhiên, mỗi món đồ chỉ được phép áp dụng thẻ nhiều nhất một lần. Thẻ này không làm thay đổi khối lượng \(W_i\) của món đồ. Quang có thể quyết định dùng hết, dùng một phần hoặc không dùng thẻ nào trong số \(K\) thẻ được tặng.

Yêu cầu: Hãy giúp Quang chọn các món đồ để cho vào vali và phân bổ \(K\) thẻ "Nhân đôi niềm vui" sao cho tổng khối lượng các món đồ không vượt quá \(M\), và tổng giá trị niềm vui mang về là lớn nhất có thể.

Input

Đọc từ tệp văn bản GIFT.INP:

• Dòng đầu tiên chứa ba số nguyên không âm \(N, M, K\) (\(1 \le N \le 2000\); \(1 \le M \le 2000\); \(0 \le K \le 5\)).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(W_i\) và \(V_i\) (\(1 \le W_i \le M\); \(1 \le V_i \le 10^7\)) lần lượt là khối lượng và giá trị niềm vui của món đồ thứ \(i\).

Output

Ghi ra tệp văn bản GIFT.OUT:

• Một số nguyên duy nhất là tổng giá trị niềm vui lớn nhất mà Quang có thể đạt được.

Example

3 5 1
4 10
3 8
2 12

32

4 10 2
4 10
3 8
5 12
6 20

60

Scoring

• Subtask 1 (\(20\%\) số điểm): \(N \le 20, M \le 100\).
• Subtask 2 (\(30\%\) số điểm): \(K = 0\).
• Subtask 3 (\(20\%\) số điểm): \(N \le 100, M \le 1000, K \le 2\).
• Subtask 4 (\(30\%\) số điểm): Không có ràng buộc gì thêm.