Để chuẩn bị cho một chuyến dã ngoại, bạn An cần mang theo một số vật dụng cần thiết. Tuy nhiên, chiếc balo của An chỉ có thể chịu được tối đa W kilogam, nên An phải lựa chọn các món đồ một cách hợp lý. Để giải quyết vấn đề cùa bạn An thì ta có *N *món đồ, mỗi món đồ thứ i có:

• Khối lượng là Wi (kg).
• Giá trị sử dụng là Vi (điểm).

Không giống như những lần trước, lần này An có yêu cầu đặc biệt: An phải chọn đúng K món đồ để mang theo.

Yêu cầu: Hãy giúp An chọn ra đúng K món đồ sao cho:

• Tổng khối lượng không vượt quá W.
• Tổng giá trị sử dụng là lớn nhất có thể.

Nếu không tồn tại cách chọn thỏa mãn, hãy in ra 0.

Dữ liệu vào:

• Dòng đầu tiên: Gồm ba số nguyên N, W, K (1≤ N ≤100; 1≤ W ≤1000; 1≤ K ≤ N).
• N dòng tiếp theo, mỗi dòng gồm hai số nguyên Wi, Vi (1≤ Wi ≤ W; 1≤ Vi ≤1000)

Dữ liệu ra: In ra một số nguyên:

• Giá trị lớn nhất đạt được.
• Hoặc 0 nếu không thể chọn đúng K món.

Ví dụ:

Input:

4 7 2

1 1

3 4

4 5

5 7

Output:

9