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

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.