Description

The space shuttle has limited volume, and carrying overly heavy items wastes a lot of fuel money. Each food item has its own volume, mass, and contained calories. Given the maximum allowable volume and mass, output the maximum total calories achievable. Each food item can be used at most once.

Input Format

The first line contains $2$ integers, representing the maximum volume $H$ and the maximum mass $T$.

The second line contains $1$ integer representing the total number of food items $n$.

The next $n$ lines each contain $3$ numbers: volume $h_i$, mass $t_i$, and contained calories $k_i$.

Output Format

One integer, representing the maximum total calories achievable (within int range).

320 350
4
160 40 120
80 110 240
220 70 310
40 400 220

550

Hint

For $100\%$ of the testdata, $H, T, h_i, t_i \le 400$, $n \le 50$, $k_i \le 500$.

Translated by ChatGPT 5