Heritage
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 [AP1] and [BPm], and a polygonal line P=[P1P2...Pm] 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 P1, P2, ..., Pm 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 v1, v2, ..., vn representing the age of the n sons. The following m lines contain each a pair of natural numbers xi, yi, representing the coordinates of the points Pi. The numbers from each line are separated by one space.
- 1 <= n <= 8
- 1 <= m <= 500
- 1 <= vi <= 50
- 0 <= x1 < x2 < ... < xm <= 32000
- 1 <= y1, y2, ..., ym <= 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.