SCUBADIV  Scuba diver
A scuba diver 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 scuba diver needs various amount of oxygen and nitrogen. The scuba diver 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 scuba diver 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 scuba diver 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 scuba diver 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 for each test case:
 reads scuba diver's demand for oxygen and nitrogen, the number of accessible cylinders and their descriptions;
 computes the minimal total weight of cylinders the scuba diver needs to complete his task;
 outputs the result.
Note: the given set of cylinders always allows to complete the given task.
Input
The number of test cases c is in the first line of input, then c test cases follow separated by an empty line.
In the first line of a test case 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; ith line contains three integers t_{i}, a_{i}, w_{i} separated by single spaces, (1 <= t_{i} <= 21, 1 <= a_{i} <= 79, 1 <= w_{i} <= 800). These are respectively: volume of oxygen and nitrogen in the ith cylinder and the weight of this cylinder.
Output
For each test case your program should output one line with the minimal total weight of cylinders the scuba diver should take to complete the task.
Example
Sample input: 1 5 60 5 3 36 120 10 25 129 5 50 250 1 45 130 4 20 119 Sample output: 249
hide comments
satoruu:
20160517 16:31:47
Learned many lessons with this problem :) 

Nikki:
20160319 09:32:42
Naive recursive 0/1 knapsack is helpful. For beginners i suggest them to read the implementation of the "Naive recursive 0/1 knapsack" until and unless they got the understanding. Then come back here and solve it in One shot. :) 

minhthai:
20160110 11:46:46
can be solve using 2d or 3d dp instead of recursive :) 

Bhuvnesh Jain:
20151029 13:58:46
Is Ankit Kumar crack person or what? You have solved the question does not mean that you spoil it for others. Always keeps on pasting links of spoj solution for every question attempted by him. Request Spoj admin to ban/ hide such links 

naruto09:
20151028 15:51:11
@ANKIT KUMAR please remove the link of solution from your comment 

tille:
20151025 19:01:06
ANKIT KUMAR why you paste the solution? you fucked up my thinking proccess. Last edit: 20151026 02:42:39 

Mohit Rathore:
20150901 12:24:39
Bottoms up solution anyone? Recursive solution ain't that satiating.


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20150728 06:49:30
2D knapsack was really great ;) 

Rishabh Joshi:
20150715 17:11:26
Very nice problem! Nice recurse.


GAURAV CHANDEL:
20150418 10:19:23
good knapsack type problem... 
Added by:  Michał Czuczman 
Date:  20040810 
Time limit:  5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  5th Polish Olympiad in Informatics, stage 2 