판옥선

이순신 장군은 판옥선이라는 특별한 전함을 전쟁에 대비해 만들었다. 판옥선의 성능을 평가하려고 조선 수병들에게 경주를 시키려 한다. n명의 수군에게 1번부터 n번까지 차례로 번호를 매긴 뒤, 각 전함에 연속된 번호의 수군들을 배정하되 그 몸무게의 합이 전함의 중량 한계 W를 넘지 않게 하려고 한다. 즉 한 전함에 배정된 수군들은 연속된 번호를 가져야 하고, 그들의 몸무게 합은 W 이하여야 한다. 전함은 충분히 많이 준비했으므로 수군이 한 명 이상 배정된 전함의 수는 중요하지 않고, 경주의 공정성, 즉 배정의 공정성이 더 중요하다. 이순신 장군은 전함별 수군 몸무게 합의 차이가 작을수록 더 공정한 배정이라고 판단했다.

더 자세히 설명하면 다음과 같다. 수군이 한 명 이상 배정된 전함의 여유중량(emptiness)은 W에서 그 전함에 배정된 수군들의 몸무게 합을 뺀 값을 제곱한 값으로 정의한다. 배정의 불공정성(unfairness)은 배정에 사용된 전함들의 여유중량 중 최댓값으로 정의한다. 이순신 장군은 불공정성이 가장 작은 배정이 가장 공정한 배정이라고 생각했다.

예를 들어 수군 3명의 몸무게가 차례대로 10, 20, 30이고 W = 50인 경우를 보자. 가능한 배정 중 하나인 {[1],[2],[3]}는 전함마다 수군을 한 명씩 배정하는 것이다. 이 배정의 불공정성은 max{(50 − 10)2, (50 − 20)2, (50 − 30)2} = 1600이다. 다른 두 가지 배정 {[1, 2],[3]}과 {[1],[2, 3]}도 가능한데, 두 배정의 불공정성은 각각 max{(50 − 30)2, (50 − 30)2} = 400과 max{(50 − 10)2, (50 − 50)2} = 1600이 된다. 그러나 수군 3명의 몸무게 합이 W = 50보다 크므로 모두를 한 전함에 배정할 수는 없다. 따라서 불공정성의 최솟값은 400이 되고, {[1, 2],[3]}이 가장 공정한 배정이 된다. 이 배정은 1번, 2번 수군을 같은 전함에, 3번 수군을 다른 전함에 배정하는 것이다.

전함의 한계 중량 W와 1번부터 n번 수군까지의 몸무게가 차례로 주어질 때, 가장 공정한 배정을 찾는 프로그램을 작성해야 한다.

입력은 표준입력을 사용한다. 첫 번째 줄에는 전함의 한계 중량 W (1 ≤ W ≤ 109)와 수군의 수 n (1 ≤ n ≤ 500,000)이 공백을 사이에 두고 차례로 주어진다. 두 번째 줄에는 수군의 몸무게가 1번 수군부터 n번 수군의 순서로 차례로 주어진다. 수군 몸무게는 1 이상 W 이하의 정수이다. 수군 한 명의 몸무게는 W보다 크지 않다.

출력은 표준출력을 사용한다. 주어진 입력에 대한 배정의 불공정성의 최솟값을 한 줄에 출력한다.