Description

After relaxing its offensive against the United Kingdom, Germany turned its spearhead to the east—the Soviet Union. In early $1943$, the fighting on the Eastern Front reached a white-hot stage. According to reliable intelligence, more than $90$ ten-thousands of German troops were preparing a massive offensive at Kursk. Therefore, Marshal Zhukov requires you to immediately transport a large amount of equipment from the Far East military factories to support the Kursk front. The train driver tells you that a single train can hold at most $V$ volume of weapons and equipment, but you might not be able to fill it up because the train cannot withstand that much weight; a single train can carry at most $G$ units of weight. Meanwhile, the factory warehouse provides you with an equipment list detailing each item's volume, weight, and firepower. To effectively support Marshal Zhukov, you need to find a plan that maximizes the total firepower.

Input Format

The first line contains two integers $V$ and $G$, representing the maximum volume and weight.

The second line contains an integer $N$, representing that the warehouse has $N$ pieces of equipment.

The $3$-rd to $N+2$-th lines each contain $3$ numbers $T_i,V_i,G_i$, representing each equipment's firepower, volume, and weight.

Output Format

Output a single number, representing the maximum total firepower that can be obtained.

6 5 
4
10 2 2
20 3 2 
40 4 3 
30 3 3 

50

Hint

Constraints: For $100\%$ of the testdata, $1\le V, G, N \le 500$, $1 \leq T_i, V_i, G_i \leq 10^9$.

Translated by ChatGPT 5