Vào buổi sáng trước ngày đi dã ngoại, PhuocThien và uou được thầy giáo giao phụ trách chuẩn bị đồ dùng cho cả nhóm. Trên bàn có \(n\) món đồ khác nhau, mỗi món đồ thứ \(i\) có khối lượng là \(w_i\) và giá trị hữu ích là \(v_i\). Chiếc ba lô mà thầy đưa cho nhóm có sức chứa tối đa là \(m\), nên không thể bỏ tất cả mọi thứ vào cùng một lúc. PhuocThien muốn chọn đúng \(k\) món đồ để mang theo, vì thầy chỉ cho phép nhóm mang một số lượng đồ vừa đủ để tránh cồng kềnh. Tuy nhiên, không phải cách chọn nào cũng hợp lệ, bởi tổng khối lượng của các món được chọn không được vượt quá \(m\). Nhiệm vụ của bạn là giúp PhuocThien tìm tổng giá trị hữu ích lớn nhất có thể đạt được khi chọn đúng \(k\) món đồ thỏa mãn điều kiện về khối lượng. Nếu không có cách chọn nào hợp lệ, hãy in ra -1.

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(m\), \(k\) (\(1 \le n \le 250\), \(1 \le k \le n\), \(1 \le m \le 2500\)).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(w_i\), \(v_i\) (\(1 \le w_i \le 1000\), \(1 \le v_i \le 10^9\)) lần lượt là khối lượng và giá trị hữu ích của món đồ thứ \(i\).

Output

• In ra một số nguyên duy nhất là tổng giá trị hữu ích lớn nhất có thể đạt được khi chọn đúng \(k\) món đồ và tổng khối lượng không vượt quá \(m\).
• Nếu không tồn tại cách chọn hợp lệ, in ra -1.

Example

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

22

9 12 1
11 -42
3 -14
10 41
9 16
10 -61
1 45
11 37
10 2
9 -43

45

Scoring

• Subtask \(1\) (\(20\%\) điểm): \(1 \le n \le 20\), \(1 \le m \le 50\), \(1 \le k \le n\).
• Subtask \(2\) (\(30\%\) điểm): \(1 \le n \le 100\), \(1 \le m \le 500\), \(1 \le k \le 20\).
• Subtask \(3\) (\(50\%\) điểm): Không có ràng buộc gì thêm.