Bạn An lên kế hoạch đi ăn vặt ở phố đi bộ. Trên phố đi bộ đó có ~R~ cửa hàng bán đồ ăn vặt. Nếu An ghé thăm cửa hàng thứ ~i~ (~1 \le i \le R~) thì:

• Mức độ vui vẻ tăng thêm ~V_i~;
• Tốn thêm ~T_i~ phút để ăn;
• Ăn được thêm ~F_i~ đơn vị thức ăn.

An muốn chọn ghé thăm một số cửa hàng sao cho:

• Tổng thời gian ăn không quá ~M~ phút;
• Tổng lượng thức ăn không quá ~U~ đơn vị;
• Mỗi cửa hàng chỉ được ghé thăm không quá một lần.

Hãy giúp An chọn một tập các cửa hàng để ghé thăm sao cho thỏa mãn điều kiện trên và tổng mức độ vui vẻ đạt được là lớn nhất.

Input

Dữ liệu vào từ tệp CAU4.INP:

• Dòng 1: gồm ba số nguyên ~M~, ~U~, ~R~ (~1 \le M \le 300~; ~1 \le U \le 100~; ~1 \le R \le 150~) lần lượt là thời gian tối đa, lượng thức ăn tối đa và số cửa hàng.
• Dòng thứ ~i~ trong ~R~ dòng tiếp theo, mỗi dòng gồm ba số nguyên ~V_i~, ~T_i~, ~F_i~:
  • ~1 \le V_i \le 10^4~ — mức độ vui vẻ nhận được khi ghé thăm cửa hàng thứ ~i~;
  • ~1 \le T_i \le M~ — thời gian ăn tại cửa hàng thứ ~i~;
  • ~1 \le F_i \le U~ — lượng thức ăn mà An ăn được khi ghé thăm cửa hàng thứ ~i~.

Output

Kết quả ghi ra tệp CAU4.OUT:

• Ghi ra một số nguyên duy nhất là tổng mức độ vui vẻ lớn nhất có thể đạt được theo yêu cầu đề bài.

Ví dụ

Ví dụ 1

Input

35 1 2
1 15 1
2 20 1

Output

2

Giải thích: Chọn ăn ở quán thứ hai:

• Tổng thời gian ăn: ~20~;
• Tổng lượng thức ăn: ~1~;
• Tổng mức độ vui vẻ: ~2~.

Ví dụ 2

Input

125 10 3
19 35 5
28 90 4
88 70 3

Output

107

Giải thích: Chọn ăn ở quán thứ nhất và quán thứ ba:

• Tổng thời gian ăn: ~35 + 70 = 105~;
• Tổng lượng thức ăn: ~5 + 3 = 8~;
• Tổng mức độ vui vẻ: ~19 + 88 = 107~.

Giới hạn

• ~1 \le M \le 300~; ~1 \le U \le 100~; ~1 \le R \le 150~.
• ~1 \le V_i \le 10^4~; ~1 \le T_i \le M~; ~1 \le F_i \le U~.
• Subtask 1: 35% điểm có ~1 \le M \le 100~; ~1 \le U \le 55~; ~1 \le R \le 12~;
• Subtask 2: 30% điểm có ~1 \le M \le 240~; ~1 \le U \le 75~; ~1 \le R \le 50~;
• Subtask 3: 35% điểm còn lại không có thêm ràng buộc bổ sung.