402492: GYM100792 F Flow Management
Description
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.
InputThe 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.
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.
3Output
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
2Note
4
11
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.