P402492 - GYM100792 F Flow Management - SSOJ - 省实信息奥赛评测系统

Memory Limit：512 MB Time Limit：2 S

Judge Style：Text Compare Creator：

Submit：0 Solved：0

上一题 Submit 下一题 Submit Record Statistics HTML

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: $\text{[math]}$ and $\text{[math]}$ . 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, $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , t — the number of household appliances with socket type $\text{[math]}$ and $\text{[math]}$ , the price of the splitter type $\text{[math]}$ to 2 and 3 pipes, the price of the splitter type $\text{[math]}$ to 2 and 3 pipes, the price of the pipe caps of type $\text{[math]}$ and $\text{[math]}$ , the price of adapters between pipe types $\text{[math]}$ and a type of the initial water socket (1 — for type $\text{[math]}$ , 2 — for type $\text{[math]}$ ) respectively. The numbers a, b and all prices are non-negative integers not exceeding 10⁹.

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 $\text{[math]}$ and b household appliances of type $\text{[math]}$ , 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 $\text{[math]}$ to two appliances and then connect an adapter from type $\text{[math]}$ to type $\text{[math]}$ to it.

402492: GYM100792 F Flow Management

Description

Source/Category

加入题单