In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].

If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.

A frogman uses a special equipment for diving. He has a cylinder with two containers: one with oxygen and the other with nitrogen. Depending on the time he wants to stay under water and the depth of diving the frogman needs various amount of oxygen and nitrogen. The frogman has at his disposal a certain number of cylinders. Each cylinder can be described by its weight and the volume of gas it contains. In order to complete his task the frogman needs specific amount of oxygen and nitrogen. What is the minimal total weight of cylinders he has to take to complete the task?

The frogman has at his disposal cylinders described below. Each description consists of: volume of oxygen, volume of nitrogen (both values are given in litres) and weight of the cylinder (given in decagrams):

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

If the frogman needs litres of oxygen and litres of nitrogen then he has to take two cylinders of total weight (for example the first and the second ones or the fourth and the fifth ones).

Write a program that:

- reads frogman's demand for oxygen and nitrogen, the number of accessible cylinders and their descriptions from the standard input;
- computes the minimal total weight of cylinders the frogman needs to complete his task;
- writes the result to the standard output.

Note: given set of cylinders always allows to complete the given task.

In the first line of the standard input there are two integers , separated by a single space, and . They denote volumes of oxygen and nitrogen respectively, needed to complete the task.

The second line contains one integer , , which is the number of accessible cylinders. The following lines contain descriptions of cylinders; -nd line contains three integers separated by single spaces, (, , ). These are respectively: volume of oxygen and nitrogen in the -th cylinder and the weight of this cylinder.

Your program should write one integer to the first and only line of the standard output. This number should be the minimal total weight of cylinders the frogman should take to complete the task.

For the input data:

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

the correct result is:

249