Panokseon

Admiral Yi Sun-sin built a special warship called the panokseon in preparation for war. To evaluate the panokseon's performance, he plans to hold a race among the Joseon sailors. After numbering the n sailors from 1 to n in order, he wants to assign consecutive-numbered sailors to each warship so that the sum of their weights does not exceed the ship's weight limit W. That is, the sailors assigned to one warship must have consecutive numbers, and the sum of their weights must be at most W. Since he has prepared enough warships, the number of warships with at least one sailor assigned does not matter; what matters more is the fairness of the race, that is, the fairness of the assignment. Admiral Yi judged an assignment to be fairer when the difference between the weight sums of the warships is smaller.

More precisely: the emptiness of a warship with at least one sailor assigned is defined as the square of the difference between W and the sum of the weights of the sailors assigned to that warship. The unfairness of an assignment is defined as the maximum of the emptiness values of the warships used in the assignment. Admiral Yi considered the assignment with the smallest unfairness to be the fairest assignment.

For example, consider the case where 3 sailors weigh 10, 20, 30 in order and W = 50. One possible assignment, {[1],[2],[3]}, puts one sailor on each warship. The unfairness of this assignment is max{(50 − 10)2, (50 − 20)2, (50 − 30)2} = 1600. The other two assignments {[1, 2],[3]} and {[1],[2, 3]} are also possible, and their unfairness values are max{(50 − 30)2, (50 − 30)2} = 400 and max{(50 − 10)2, (50 − 50)2} = 1600 respectively. However, since the total weight of the 3 sailors is greater than W = 50, they cannot all be assigned to one warship. Therefore the minimum unfairness is 400, and {[1, 2],[3]} is the fairest assignment. This assignment puts sailors 1 and 2 on the same warship and sailor 3 on another.

Given the weight limit W of the warships and the weights of sailors 1 through n in order, you must write a program that finds the fairest assignment.

The input is read from standard input. The first line gives the weight limit W (1 ≤ W ≤ 109) and the number of sailors n (1 ≤ n ≤ 500,000), separated by a space. The second line gives the weights of the sailors in order from sailor 1 to sailor n. Each sailor's weight is an integer between 1 and W inclusive. No single sailor weighs more than W.

The output is written to standard output. Print the minimum unfairness of an assignment for the given input on one line.