Maximizing Firepower for the Kursk Front

In early 1943, the Eastern Front battles intensified. After easing the offensive against Britain, Germany shifted its focus to the Soviet Union. Reliable intelligence revealed that over 900,000 German troops were assembling in Kursk for a massive offensive. Marshal Zhukov has now ordered you to transport a large amount of military equipment from the Far Eastern factories to support the Kursk front.

A train is available for this mission. It can accommodate equipment with a total volume of at most \(V\) units. However, due to weight limitations, the train can carry at most \(G\) units of weight in a single trip. The arms factory warehouse provides you with a list of equipment items, each with its volume, weight, and firepower value. Your task is to select a subset of these items such that the total firepower is maximized, without exceeding the train's volume and weight capacities.

This is essentially a two-dimensional knapsack problem where the objective is to maximize the total firepower.

inputFormat

The input consists of multiple lines. The first line contains two integers \(V\) and \(G\)\(,\) where \(V\) is the maximum volume capacity of the train and \(G\) is the maximum weight capacity. The second line contains a single integer \(n\), the number of equipment items available. Then \(n\) lines follow. Each of these lines contains three integers: the volume, weight, and firepower of an equipment item, respectively.

outputFormat

Output a single integer, which is the maximum total firepower that can be achieved without exceeding the capacity of the train, both in terms of volume and weight.

sample

10 20
3
5 7 10
4 5 8
2 10 5

18