What is the minimal total weight of cylinders

Reference no: EM13161165

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):

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; i-th 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 i-th 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

Reference no: EM13161165

Questions Cloud

Method called wordlengths that accepts a scanner : Write a method called wordLengths that accepts a Scanner representing an input file as its argument. Your method should read from the given file.

Method named isallvowels that returns : Write a method named isAllVowels that returns whether a String consists entirely of vowels (a, e, i, o, or u, case-insensitively). If every character of the String is a vowel, your method should return true. If any character of the String is a non-vo..

Multidimensional arrays : multidimensional arrays to life, let's consider a specific example: How can you visualize a 4-dimensional array? How can you give meaning to each dimension this array has? What kind of application would such an array be useful for?

What is the energy required to move a mole of urea out : What is the energy required to move a mole of urea out of the kidney cells and into the urine?

What is the minimal total weight of cylinders : 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 ..

Create a file, shared.txt : When your program starts, it shall do the following:1. Create a file, SHARED.txt, in the current directory (cwd). 2. Write it's pid (Process ID) followed by a Carriage Return and Newline in the file.

State divers breathing compressed air : The solubility of N2 in blood can be a serious problem (the "bends") for divers breathing compressed air (78% N2 by volume) at depths greater than 50 ft.

Hasanodddigit that returns whether any digit : d named hasAnOddDigit that returns whether any digit of a positive integer is odd. Your method should return true if the number has at least one odd digit and false if none of its digits are odd. 0, 2, 4, 6, and 8 are even digits, and 1, 3, 5, 7, 9 a..

Determine the microcanonical partition function : Determine the microcanonical partition function, omega. Determine fundamental relation of system, using Stirling's approximation Determine the energy and heat capacity for the system as a function of temperature using Stirling's approximation. Det..

User Account

All Pages