Background

NASA (National Aeronautics and Space Administration) has long struggled with safety technologies such as the thermal protection tiles on the space shuttle. Under various pressures, the history of the space shuttle program was brought to an end. However, no one can guarantee that similar issues will not occur in the future. Thus, when such spaceflight problems arise, astronauts may have to perform extravehicular repairs. Excessive repairs, however, consume a large amount of the astronauts’ energy. Therefore, NASA wants to design a food plan to load as many high-calorie foods as possible under limited volume and load-bearing capacity.

Problem 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