시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 2048 MB199844.444%

문제

You have $N$ magic squares (numbered from $1$ to $N$). For each magic square, you can set the length of its side to any non-negative integers. The cost of each magic square is proportional to its area; magic square $i$ has a cost of $C_i$ per unit area. In other words, if the length of magic square $i$ is set to $k$, then it will cost you $k^2 \cdot C_i$.

You want to build a wall with a length of $D$ using these magic squares. You have to line up all your magic squares next to each other, and their total length has to be exactly $D$. The base of each magic square must fully touch the floor, i.e. you are not allowed to rotate the magic squares.

Determine the minimum total cost to build the wall.

입력

This problem has multiple test cases. The first line consists of an integer $T$ ($1 ≤ T ≤ 20$), which represents the number of test cases.

Each test case consists of two lines. The first line consists of two integers $N$ $D$ ($1 ≤ N ≤ 10\, 000$; $1 ≤ D ≤ 10^7$). The second line consists of $N$ integers $C_i$ ($1 ≤ C_i ≤ 10\, 000$).

출력

For each test case, output an integer in a single line representing the minimum total cost to build the wall.

예제 입력 1

3
3 5
500 1000 100
1 4
30
4 4
30 30 30 30

예제 출력 1

2100
480
120

For the first test case, set the length of the side of magic square $1$, $2$ and $3$ to $1$, $0$, and $4$, respectively. The total cost to build the wall is $1^2 \cdot 500 + 0^2 \cdot 1000 + 4^2 \cdot 100 = 2100$, which can be shown to be the minimum.

For the second test case, the only solution is to set the length of the side of magic square $1$ to $4$. The total cost to build the wall is $4^2 \cdot 30 = 480$.

For the third test case, set the length of the side of all magic squares to $1$. The total cost to build the wall is $120$, which can be shown to be the minimum.

예제 입력 2

3
10 20
1 2 3 4 5 6 7 8 9 10
10 100
1 2 3 4 5 6 7 8 9 10
1 10000000
10000

예제 출력 2

140
3419
1000000000000000000