Diver

Problem Background

Special for beginners, ^_^

Problem Description

A diver uses special equipment to dive. He has cylinders with $2$ kinds of gas: one for oxygen, one for nitrogen. To dive to a certain depth requires various amounts of oxygen and nitrogen. The diver has a certain number of cylinders. Each cylinder has a weight and a gas capacity. What is the minimum total weight of cylinders the diver needs to complete his work?

Example: the diver has $5$ cylinders. Each line has three numbers: oxygen, nitrogen (in liters), and cylinder weight:

3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

If the diver needs at least 5 liters of oxygen and 60 liters of nitrogen, the minimum total weight is 249 (using cylinders 1, 2 or 4, 5).

Your task is to compute the minimum total weight of cylinders the diver needs to complete his work.

Input Format

The first line has $2$ integers $m,n\ (1\le m\le 21,\ 1\le n\le 79)$ — the required amounts of oxygen and nitrogen respectively.

The second line is an integer $k\ (1\le k\le 1000)$ — the number of cylinders.

The following $k$ lines each contain $3$ integers $a_i,b_i,c_i\ (1\le a_i\le 21,\ 1\le b_i\le 79,\ 1\le c_i\le 800)$ — the oxygen capacity, nitrogen capacity, and weight of the $i$-th cylinder.

Output Format

One line containing a single integer — the minimum total weight of cylinders needed.

Sample Input

5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

Sample Output

249

Constraints

$1\le m\le 21$, $1\le n\le 79$, $1\le k\le 1000$, $1\le a_i\le 21$, $1\le b_i\le 79$, $1\le c_i\le 800$.

Time limit 1s, memory limit 1024KiB for each test case.