P1507 NASA's Food Plan

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.

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.

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$.

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

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