402492: GYM100792 F Flow Management

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Flow Managementtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Mario is doing plumbing works in his house in order to connect various household appliances to the water supply.

There are two water socket types available: and . One initial socket of type t is already connected to the supply system, but Mario has a appliances that require sockets of the first type and b appliances that require sockets of the second type.

Mario uses standard parts for his work:

  • A pipe splitter allows one to replace one socket with several sockets of the same type. For both types, splitters into two and into three pipes are available.
  • A pipe adapter replaces any single socket of any type with a socket of another type.
  • A pipe cap is used to close any single socket. Different types of caps are used for different types of sockets.

Each part has a predefined price at the nearest DIY market. You may assume that there is an unlimited number of parts of each kind available.

Mario is known to be a big miser, therefore he wants you to help him determine the minimum amount of money he has to spend to connect his appliances with a sockets of the first type and b sockets of the second type. No socket can be left open and unused, or water will flow out of it.

Input

The first line of the input contains a single integer n — the number of test cases you are to solve (1 ≤ n ≤ 50 000). Each of the following n lines contains ten integers: a, b, , , , , , , , t — the number of household appliances with socket type and , the price of the splitter type to 2 and 3 pipes, the price of the splitter type to 2 and 3 pipes, the price of the pipe caps of type and , the price of adapters between pipe types and a type of the initial water socket (1 — for type , 2 — for type ) respectively. The numbers a, b and all prices are non-negative integers not exceeding 109.

Output

For each of n test cases print a line containing a single integer — the minimum amount of money that Mario has to spend in order to buy all necessary tools to assemble a pipeline from a given water socket to his a household appliances of type and b household appliances of type , without leaving any socket open and unused.

ExamplesInput
3
1 1 1 1 1 1 1 1 1 1
2 3 5 6 3 1 2 1 1 2
0 3 10 10 5 8 6 4 3 1
Output
2
4
11
Note

In the first sample you need to install a single splitter of type to two appliances and then connect an adapter from type to type to it.

加入题单

上一题 下一题 算法标签: