Problem - 100792F - Codeforces

2015-2016 ACM-ICPC, NEERC, Moscow Subregional Contest
Finished

→ About Contest

The contest was hosted by Moscow State University, Moscow Institute of Physics and Technology and Higher School of Economics.

Contest website

→ Virtual participation

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests. If you've seen these problems, a virtual contest is not for you - solve these problems in the archive. If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive. Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

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.

Examples

Input

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.