Description

A diver uses special equipment for diving. He has a cylinder with two types of gases: one for oxygen and one for nitrogen. The depth the diver can descend requires specific amounts of oxygen and nitrogen. The diver has a certain number of cylinders. Each cylinder has a weight and gas capacity. To complete his task, the diver needs a specific amount of oxygen and nitrogen. What is the minimum total weight of cylinders he needs to accomplish his task?

For example: The diver has 5 cylinders. Each line contains three numbers representing the oxygen, nitrogen (in liters), and the weight of the cylinder:
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

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

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

Input Format

The first line contains two integers, m and n (1 ≤ m ≤ 21, 1 ≤ n ≤ 79), representing the required amounts of oxygen and nitrogen, respectively.
The second line contains an integer k (1 ≤ k ≤ 1000), representing the number of cylinders.
The following k lines each contain three integers, $a_i$, $b_i$, and $c_i$ (1 ≤ $a_i$ ≤ 21, 1 ≤ $b_i$ ≤ 79, 1 ≤ $c_i$ ≤ 800), representing the oxygen capacity, nitrogen capacity, and weight of the i-th cylinder, respectively.

Output Format

A single line containing an integer, the minimum total weight of cylinders required for the diver to complete his task.

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

249