Although she tries very hard, Cecilia Alcott is not the best at cooking. Luckily, to gain favor with Ichika, she doesn't need skills — she has money. Cecilia has secured a date with Ichika today, and so she is planning to treat him to a series of fancy restaurants over the course of this evening.

There are ~R~ restaurants Cecilia has in mind. Each restaurant has an impression value ~V_i~, which is how much of an impression Cecilia will make on Ichika if they eat there. As much as Cecilia would like to visit them all with Ichika, she can only spend at most ~M~ minutes with Ichika this evening. As such, she has also recorded the time it takes to eat at each restaurant, ~T_i~, which is in minutes. Another concern is that Ichika's stomach has a finite capacity, and so he can only eat up to ~U~ units of food before becoming full. If he becomes full, he will request to go home early. Ichika will also politely decline to go to a restaurant if it will serve more food than he can finish. As Cecilia doesn't want to make Ichika unhappy, she agrees to end the date if either of these situations occur. Hoping to be prepared for such a situation, Cecilia has also recorded the units of food served at each restaurant, ~F_i~.

Cecilia would now like to know at most how much of an impression she can make on Ichika this evening, if they dine at each restaurant at most once.

Input Specification

The first line of input will contain three integers, ~M~, ~U~, and ~R~.

The next ~R~ lines will each contain 3 integers, ~V_i~, ~T_i~, and ~F_i~.

Output Specification

The output should be a single line, the most impression Cecelia can make on Ichika this evening, following the constraints explained above.

Constraints

~1 \le V_i \le 10\,000~

~1 \le T_i \le M~

~1 \le F_i \le U~

Test Case Batch	Marks	Constraints
1 [10 cases]	60	~1 \le M \le 100; 1 \le U \le 55; 1 \le R \le 12~
2 [3 cases]	30	~1 \le M \le 240; 1 \le U \le 75; 1 \le R \le 50~
3 [3 cases]	10	~1 \le M \le 300; 1 \le U \le 100; 1 \le R \le 150~

Sample Input 1

15 1 2
1 5 1
2 10 1

Sample Output 1

2

Explanation for Sample Output 1

Since Ichika becomes full after eating at any of the two restaurants, Cecilia should take him to the second one, because even if it takes twice as long to eat there as the first restaurant, it also yields twice the impression value.

Sample Input 2

120 10 3
10 30 5
25 70 3
30 90 4

Sample Output 2

40

Explanation for Sample Output 2

Cecilia should choose the first and third restaurants, using up all 120 minutes while making sure Ichika only gets 9 units of food. This results in the total value of 40.