Ăn vặt

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ò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\)) - 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\).

Ràng buộc:

• Subtask 1: \(35\%\) số điểm, \(1 \le M \le 100\), \(1 \le U \le 55\), \(1 \le R \le 12\);

• Subtask 2: \(30\%\) số điểm, \(1 \le M \le 240\), \(1 \le U \le 75\), \(1 \le R \le 50\);

• Subtask 3: \(35\%\) số điểm còn lại không có thêm ràng buộc bổ sung.

Output

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.

Example 1

Input:

35 1 2
1 15 1
2 20 1

Output:

2

Example 2

Input:

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

Output:

107

Note

Ví dụ 1: chọn ăn ở quán thứ hai: tổng thời gian ăn là \(20\), tổng lượng thức ăn là \(1\), tổng mức độ vui vẻ là \(2\).

Ví dụ 2: chọn ăn ở quán thứ nhất và quán thứ ba: tổng thời gian ăn là \(35 + 70 = 105\), tổng lượng thức ăn là \(5 + 3 = 8\), tổng mức độ vui vẻ là \(19 + 88 = 107\).