Heritage

The old Count D owns a piece of land that he wants to divide among his $n$ sons.

The land lies above the $Ox$ axis. Its lower boundary is the horizontal segment $[AB]$ on the $Ox$ axis, its left and right boundaries are the vertical segments $[AP_1]$ and $[BP_m]$, and its upper boundary is the polygonal line $P_1P_2\dots P_m$, which lies entirely above the $Ox$ axis.

The Count builds $n-1$ vertical fences. Each fence joins the base segment $[AB]$ to the polygonal line, so a fence placed at coordinate $x$ has length equal to the height of the polygonal line at $x$. The fences split the land into $n$ parcels, ordered from left to right.

The parcelling must satisfy both of the following conditions:

1. The parcels can be assigned to the sons so that each son's parcel has an area directly proportional to his age.
2. Among all parcellings that satisfy condition 1, the total length of the fences is as small as possible.

Given the $m$ points $P_1, \dots, P_m$ and the ages of the $n$ sons, compute the minimum possible total fence length.

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers $v_1, v_2, \dots, v_n$ — the ages of the sons.

Each of the next $m$ lines contains two integers $x_i$ and $y_i$ — the coordinates of point $P_i$.

Print a single real number: the minimum possible total length of the $n-1$ fences, rounded to exactly 6 decimal places.

• $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$
• Fence widths are negligible.
• Use double-precision floating point for the computation.

In the sample (the first example, $n = 2$) only one fence is needed.

Placing the fence at $x = 10$, where the polygonal line has height $1$, gives a total fence length of $1.000000$. The son aged $4$ takes the left parcel (area $16$) and the son aged $2$ takes the right parcel (area $8$); both areas are proportional to the ages.

If the fence were placed instead at $x \approx 6.54984$ (length $\approx 2.51661$), the son aged $2$ would take the left parcel and the son aged $4$ the right one. That split still satisfies the area-proportionality condition, but its fence is longer, so it is not optimal. Every other position fails the area-proportionality condition.