31103번 - Gas and Minerals 다국어

문제

An Artifact that could turn the tide of the war was discovered in one of the distant Terran colonies. Meanwhile, the intelligence service reports that a Zerg swarm is moving towards the colony. It is necessary to protect the Artifact at all costs before the arrival of reinforcements.

You have $m$ units of minerals and $g$ units of Vespen gas. In addition, there are $n$ types of defensive buildings available for construction. A building of type $i$ requires $a_i$ units of minerals and $b_i$ units of gas to construct, and increases the defenses of the base by $c_i$ units. You can construct any number of buildings (including zero) of any type, provided that the total costs of minerals and gas for all buildings will not exceed $m$ and $g,ドル respectively.

Determine what the maximum total building defense capability can be achieved under the given constraints.

입력

The first line contains three integers $m,ドル $g$ and $n$ --- the number of available units of minerals and gas, respectively, and the number of building types (0ドル \le m \le 1000,ドル 0ドル \le g \le 1000,ドル 1ドル \le n \le 10$).

The $i$ th of the following $n$ lines contains three integers $a_i,ドル $b_i$ and $c_i$ --- the amount of units of mineral and gas are needed to construct a building of the $i$-th type and its defenses (1ドル \le a_i \le 100,ドル 0ドル \le b_i \le 100,ドル 0ドル \le c_i \le 100$).

출력

Print a single integer --- the maximum total building defense capability that can be achieved.

제한

노트

In the first example, the optimum is provided by the construction of one building of type 2ドル$ and one building of type 3ドル$.

In the second example, it is most profitable to construct one building of type 1ドル$ and two buildings of type 3ドル$.