Score: $300$ points

问题陈述

为 $T$ 个测试案例解决以下问题。

在美食评论网站 EatCocoder 上，您可以用从 $1$ 到 $5$ 的整数星级来评价餐厅。 最初，由厨师 B 管理的餐厅有 $A_i$ 条 $i$ 星级的评论。$(1 \le i \le 5)$ 厨师可以向 EatCocoder 管理层支付 $P_i$ 日元的贿赂，以获得额外的一条 $i$ 星级评论。$(1 \le i \le 5)$

通过贿赂总共增加 $k$ 条评论后，将总共有 $A_1+A_2+A_3+A_4+A_5+k$ 条评论。 厨师 B 希望这些评论的平均评分至少为 3 星级。确定实现此目的所需的最少贿赂总额。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

Solve the following problem for $T$ test cases.

On the gourmet review site EatCocoder, you can review restaurants with an integer number of stars from $1$ to $5$.
Initially, the restaurant managed by Chef B has $A_i$ reviews with $i$ stars. $(1 \le i \le 5)$
The chef can pay a bribe of $P_i$ yen to the EatCocoder administration to have one additional $i$-star review. $(1 \le i \le 5)$

After adding a total of $k$ reviews by bribery, there will be $A_1+A_2+A_3+A_4+A_5+k$ reviews in total.
Chef B wants the average rating of these reviews to be at least $3$ stars. Determine the minimum total amount of bribery required to achieve this.

Constraints

• All input values are integers.
• $1 \le T \le 10^4$
• $0 \le A_i \le 10^8$
• $1 \le A_1+A_2+A_3+A_4+A_5$
• $1 \le P_i \le 10^8$

Input

The input is given from Standard Input in the following format:

$T$

$\rm{Case}_1$

$\rm{Case}_2$

$\vdots$

$\rm{Case}$$_T$

Here, $\rm{Case}$$_i$ represents the $i$-th test case.

Each test case is given in the following format:

$A_1$ $A_2$ $A_3$ $A_4$ $A_5$

$P_1$ $P_2$ $P_3$ $P_4$ $P_5$

Output

Print $T$ lines in total.
The $i$-th line should contain the answer to the $i$-th test case as an integer.

Sample Input 1

6
1 0 1 0 0
1 2 3 4 5
0 2 2 0 0
1 1 1 1 5
0 1 2 0 0
1 1 1 5 3
1 1 1 0 0
1 1 1 1 1
0 0 0 0 1
1 1 1 1 1
100000000 100000000 100000000 0 0
100000000 100000000 100000000 100000000 100000000

Sample Output 1

5
2
3
2
0
15000000000000000

This input contains six test cases.

• For the first test case, you can, for example, do the following to have an average rating of at least $3$ stars with a bribe of $5$ yen, which is the minimum possible amount.
  • Initially, there are $1,0,1,0,0$ reviews with $1,2,3,4,5$ stars, respectively.
  • Pay a bribe of $P_5 = 5$ yen to add one $5$-star review.
  • As a result, there are $1,0,1,0,1$ reviews with $1,2,3,4,5$ stars, respectively, averaging $3$ stars.
• For the second test case, you can, for example, do the following to have an average rating of at least $3$ stars with a bribe of $2$ yen, which is the minimum possible amount.
  • Initially, there are $0,2,2,0,0$ reviews with $1,2,3,4,5$ stars, respectively.
  • Pay a bribe of $P_4 \times 2 = 2$ yen to add two $4$-star reviews.
  • As a result, there are $0,2,2,2,0$ reviews of with $1,2,3,4,5$ stars, respectively, averaging $3$ stars.
• For the third test case, you can, for example, do the following to have an average rating of at least $3$ stars with a bribe of $3$ yen, which is the minimum possible amount.
  • Initially, there are $0,1,2,0,0$ reviews with $1,2,3,4,5$ stars, respectively.
  • Pay a bribe of $P_5 = 3$ yen to add one $5$-star review.
  • As a result, there are $0,1,2,0,1$ reviews with $1,2,3,4,5$ stars, respectively, averaging $3.25$ stars.
• For the fourth test case, you can, for example, do the following to have an average rating of at least $3$ stars with a bribe of $2$ yen, which is the minimum possible amount.
  • Initially, there are $1,1,1,0,0$ reviews with $1,2,3,4,5$ stars, respectively.
  • Pay a bribe of $P_4 = 1$ yen to add one $4$-star review.
  • Pay a bribe of $P_5 = 1$ yen to add one $5$-star review.
  • As a result, there are $1,1,1,1,1$ reviews with $1,2,3,4,5$ stars, respectively, averaging $3$ stars.
• For the fifth test case, you can, for example, do the following to have an average rating of at least $3$ stars with a bribe of $0$ yen, which is the minimum possible amount.
  • Initially, there are $0,0,0,0,1$ reviews with $1,2,3,4,5$ stars, respectively.
  • Since the average is already $5$, which is not less than $3$, give no bribe.
• For the sixth test case, note that the answer may not fit into a $32$-bit signed integer.