The old Count D has a surface of land which he wants to leave as heritance to his n sons. The surface is delimited by an horizontal segment [AB] placed on the Ox axis, two vertical segments [AP₁] and [BP_m], and a polygonal line P=[P₁P₂...P_m] placed entirely upside the Ox axis. The Count D builds n-1 vertical fences each of them connecting the [AB] segment with the polygonal line P. As a result n parcels of land with different areas will be created and left as heritage to his sons. The Count D wishes that the following two conditions should be respected:

    1. Each son should receive a parcel with an area directly proportional with his age.
    2. The sum of the fences' lengths should be minimal.

Knowing the coordinates of the m points P₁, P₂, ..., P_m and his n sons' age, a parcelling, that respects the two conditions, must be determined.

Input

On the first line there are two natural numbers n and m with the meaning above. The following line contains n natural numbers v₁, v₂, ..., v_n representing the age of the n sons. The following m lines contain each a pair of natural numbers x_i, y_i, representing the coordinates of the points P_i. The numbers from each line are separated by one space.

    - 1 <= n <= 8
    - 1 <= m <= 500
    - 1 <= v_i <= 50
    - 0 <= x₁ < x₂ < ... < x_m <= 32000
    - 1 <= y₁, y₂, ..., y_m <= 32000
    - The width of the fences are ignorable;
    - Each value will be assessed with a precision of 0.001;
    - For the contestants that use C/C++ , it is recommended the double type.
    - Your program will obtain a score if the output respects both conditions;

Output

The output will have two lines. The first line will contain a real number representing the sum of the fences' lengths. The second will contain n-1 real numbers. The k-th number (k=1, 2, ..., n-1) will represent the coordinate of the k-th fence on the Ox axis. The numbers from the second line will be given in the increasing order and will be separated by one space.

Constraints

Time limit: 1 second
Memory limit: 64 megabytes

Examples

input
2 4
4 2
2 1
8 3
10 1
14 3

output
1.000000
10.00

The (one) fence is built at x=10.00000 (view image), the 4 years old son will receive the parcel from the left and the 2 years old son will receive the parcel from the right. This way both conditions are respected.