히스토그램

구간 $[1, n]$의 자연수를 데이터 값이라 하고, 데이터 값 $i$가 수열에 나타난 횟수를 데이터 값 $i$의 빈도 $f_i$라 하자. 예를 들어 수열 $[3, 2, 3, 2, 4, 2]$에서 데이터 값 $2$의 빈도는 $3$이다. 다음 빈도표는 구간 $[1, 8]$에 있는 값들의 빈도이다.

버킷 $b_i$는 구간 $[s_i , e_i]$와 대푯값 $r_i$로 나타낸다. 각 버킷의 대푯값으로는 평균 빈도를 사용한다. 버킷들의 구간이 서로 겹치지 않고 빈도표에 있는 모든 데이터 값의 범위를 덮도록, 적은 수의 버킷으로 이루어진 히스토그램으로 빈도표를 나타내려고 한다. 예를 들어 위 빈도표를 두 개의 버킷으로 나타낸 히스토그램의 한 예에서 첫 번째와 두 번째 버킷은 각각 값의 범위 $[1, 4]$와 $[5, 8]$을 덮는다. 이 히스토그램에서 첫 번째와 두 번째 버킷의 평균 빈도는 각각 $3.75$와 $9.75$이다.

빈도표로부터 버킷의 집합을 구성한 뒤 어떤 값의 빈도를 물으면, 그 값이 속한 버킷의 평균 빈도를 답해야 한다. 예를 들어 값 $2$의 빈도를 물으면 값 $2$는 평균 빈도가 $3.75$인 첫 번째 버킷에 속하므로, 값 $2$의 실제 빈도 $2$ 대신 $3.75$를 답한다. 히스토그램에서 버킷의 오차는 그 버킷에 속한 모든 값의 빈도에 대한 제곱 오차의 합으로 정의한다. 위 히스토그램에서 구간 $[1, 4]$에 대한 첫 번째 버킷의 오차는 $(4 - 3.75)^2$ $+$ $(2 - 3.75)^2$ $+$ $(3 - 3.75)^2$ $+$ $(6 - 3.75)^2$ $=$ $8.75$이고, 구간 $[5, 8]$에 대한 두 번째 버킷의 오차는 $(5 - 9.75)^2$ $+$ $(6 - 9.75)^2$ $+$ $(12 - 9.75)^2$ $+$ $(16 - 9.75)^2$ $=$ $80.75$이다. 히스토그램의 오차는 히스토그램에 있는 모든 버킷의 오차의 합으로 정의한다. 따라서 이 히스토그램의 오차는 $8.75 + 80.75 = 89.5$이다. 한편 다음 히스토그램의 오차는 $21.333333$이며, 이는 두 개의 버킷으로 이루어진 히스토그램의 오차 중 최솟값이다.

빈도표와 히스토그램의 버킷 수 $B$가 주어질 때, 버킷이 최대 $B$개인 히스토그램 중 오차가 최소인 히스토그램을 찾는 프로그램을 작성하라.

표준 입력에서 입력을 읽는다. 입력의 첫째 줄에는 정수 $B$ ($1 \le B \le 30$)가 주어지며, $B$는 버킷 수의 한계이다. 둘째 줄에는 정수 $n$ ($1 \le n \le 4,000$)이 주어지며, 이는 데이터 값의 수로 범위 $[1, n]$을 나타낸다. 다음 $n$개 줄에는 데이터 값의 빈도가 주어진다. 그중 $i$번째 줄에는 데이터 값 $i$의 빈도 $f_i$인 양의 정수가 주어지며, $1 \le f_i ≤ 100$이다.

표준 출력에 출력한다. 정확히 한 줄을 출력한다. 그 줄에는 오차가 최소인 히스토그램의 오차값 $OPT$를 나타내는 실수 $z$를 출력한다. 출력 $z$는 정수 부분, 소수점, 소수 부분으로 이루어진 형식이어야 하며, $OPT - 10^{-4} < z < OPT + 10^{-4}$를 만족해야 한다.