유산

D 백작은 자신이 가진 땅을 $n$명의 아들에게 물려주려고 한다.

이 땅은 $Ox$ 축 위쪽에 있다. 아래쪽 경계는 $Ox$ 축 위의 수평 선분 $[AB]$이고, 왼쪽과 오른쪽 경계는 각각 수직 선분 $[AP_1]$과 $[BP_m]$이며, 위쪽 경계는 완전히 $Ox$ 축 위쪽에 놓인 꺾은선 $P_1P_2\dots P_m$이다.

백작은 $n-1$개의 수직 울타리를 세운다. 각 울타리는 바닥 선분 $[AB]$와 꺾은선을 잇는다. 따라서 $x$ 좌표에 세운 울타리의 길이는 그 지점에서 꺾은선의 높이와 같다. 이 울타리들은 땅을 왼쪽에서 오른쪽으로 $n$개의 구역으로 나눈다.

이 분할은 다음 두 조건을 모두 만족해야 한다.

1. 각 아들에게 구역을 하나씩 배정할 때, 아들이 받는 구역의 넓이가 그 아들의 나이에 정비례하도록 배정할 수 있어야 한다.
2. 위 조건을 만족하는 모든 분할 중에서, 울타리들의 길이 합이 최소가 되어야 한다.

$m$개의 점 $P_1, \dots, P_m$의 좌표와 $n$명의 아들의 나이가 주어질 때, 가능한 울타리 길이 합의 최솟값을 구하라.

첫째 줄에 두 정수 $n$과 $m$이 주어진다.

둘째 줄에 $n$개의 정수 $v_1, v_2, \dots, v_n$이 주어지며, 이는 각 아들의 나이이다.

이어지는 $m$개의 줄에는 각각 두 정수 $x_i$와 $y_i$가 주어지며, 이는 점 $P_i$의 좌표이다.

울타리 $n-1$개의 길이 합의 최솟값을 소수점 아래 여섯째 자리까지 반올림하여 실수 하나로 출력한다.

• $1 \le n \le 8$
• $1 \le m \le 500$
• $1 \le v_i \le 50$
• $0 \le x_1 < x_2 < \dots < x_m \le 32000$
• $1 \le y_1, y_2, \dots, y_m \le 32000$
• 울타리의 두께는 무시한다.
• 계산에는 배정밀도(double) 부동소수점을 사용하는 것을 권장한다.

예시(첫 번째 예제, $n = 2$)에서는 울타리가 하나만 필요하다.

울타리를 $x = 10$에 세우면 그 지점에서 꺾은선의 높이가 $1$이므로 전체 울타리 길이는 $1.000000$이다. 나이가 $4$인 아들은 왼쪽 구역(넓이 $16$)을, 나이가 $2$인 아들은 오른쪽 구역(넓이 $8$)을 받으며, 두 구역의 넓이는 나이에 정비례한다.

만약 울타리를 $x \approx 6.54984$에 세우면(길이 $\approx 2.51661$) 나이가 $2$인 아들이 왼쪽, 나이가 $4$인 아들이 오른쪽 구역을 받는다. 이 분할도 넓이 정비례 조건은 만족하지만 울타리가 더 길어서 최적이 아니다. 그 밖의 위치는 넓이 정비례 조건을 만족하지 못한다.