#MORIA2. Mines of Moria II

    ID: 3938 远端评测题 5000ms 1536MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>dynamic-programmingquadrangle-inequality

Mines of Moria II

This problem is similar but not identical to the problem MORIA.

In the Mines of Moria, the job of Gakrobera Silverborn the dwarf is still to load minecarts with N stones. The stones are numbered, from 1 to N, and a given minecart can only be loaded with consecutive stones.

The minecart have an optimal load L.1 Each stone has an integer weight between 1 kg and L kg. The score of a minecart loaded with W kg of stones is (W − L)2. After all stones have been loaded in minecarts, the total score is the sum of the score of each minecarts. The lower the total score is, the better it is.

To help Gakrobera, find the best possible way to load minecarts, given the weights of each stone from 1 to N.

For example, with an optimal load L = 2000 kg, given four stones of 700 kg, Gakrobera will prefer to load them all in a single minecart (total score 8002 = 640 000). But given four stones of 800 kg, Gakrobera will prefer to load two minecarts with two stones (total score 4002 + 4002 = 320 000).

Beware: the situation in the Mines of Moria has gone wild, the Dwarves push cupidity too far, the optimal load can be very high! The Balrog will soon be awaken…

Input

The input begins with an integer T (1 ≤ T ≤ 1000), the number of test cases. Then T test cases follow.

Each test case is a line of space-separated integers. The first integer L (1 ≤ L ≤ 106) is the optimal load. The second integer N (1 ≤ N ≤ 106) is the number of stones to be loaded. Next come N integers w1, …, wN (1 ≤ wi L), where wi is the weight of the stone i.

Output

For each test case, output the smallest possible total score.

Example

input
3
2000 4 700 700 700 700
2000 4 800 800 800 800
2000 10 100 200 300 400 500 600 700 800 900 1000

output 640000 320000 270000

</p>

Compared to the situation in the problem MORIA, the optimal load is not fixed.