Polish version    English version  
  History of OI -> V OI 1997/1998 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
Stage III - results
Stage II - results
Stage I - results
Problems
Regulations
Schedule
Stats
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
Niebieskie ksi.eczki
V Olimpiada Informatyczna 1997/1998

Task: PLE
Author:
Frogman

II stage contest  

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?

Example

The frogman has at his disposal 5 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 5 litres of oxygen and 60 litres of nitrogen then he has to take two cylinders of total weight 249 (for example the first and the second ones or the fourth and the fifth ones).

Task

Write a program that:

  • reads frogman's demand for oxygen and nitrogen, the number of accessible cylinders and their descriptions from the text file PLE.IN;
  • computes the minimal total weight of cylinders the frogman needs to complete his task;
  • writes the result to the text file PLE.OUT.
Note: given set of cylinders always allows to complete the given task.

Input

In the first line of the input file PLE.IN there are two integers t, a separated by a single space, 1<=t<=21 and 1<=a<=79. They denote volumes of oxygen and nitrogen respectively, needed to complete the task. The second line contains one integer n, 1<=n<=1000, which is the number of accessible cylinders. The following n lines contain descriptions of cylinders; (i+2)-nd line of the file PLE.IN contains three integers ti, ai, wi separated by single spaces, (1<=ti<=21, 1<=ai<=79, 1<=wi<=800). These are respectively: volume of oxygen and nitrogen in the i-th cylinder and the weight of this cylinder.

Output

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

Example

For the input file PLE.IN:

5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
the correct result is the output file PLE.OUT:
249




Print friendly version