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 toward the colony. The artifact must be protected at all costs before reinforcements arrive.

You have $m$ units of minerals and $g$ units of Vespen gas. 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 may construct any number of buildings of any type, including zero, as long as the total minerals and total gas spent do not exceed $m$ and $g$, respectively.

Determine the maximum total defense capability that can be achieved under these constraints.

The first line contains three integers $m$, $g$, and $n$, the units of minerals and gas available 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 units of minerals and gas needed to construct a building of type $i$, and its defense value ($1 \le a_i \le 100$, $0 \le b_i \le 100$, $0 \le c_i \le 100$).

Output

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