URI Online Judge | 1912

Help Seu Madruga

By Dâmi Henrique, Inatel BR Brazil

Timelimit: 4

Madruga finally got a job, that’s his big chance to pay the 14 months of rent that are late. He is a paper cutter and he is getting lots of money with this job.

Madruga will receive N rectangular strips of paper of 1 centimeter(cm) of width and C cm of length. The strips should be placed one beside the other so that their bases are aligned(check the image). The task is, with only one straight cut, parallel to the base, Madruga needs to make the sum of the areas of the cut strips equal to A cm².

See the illustration below with N = 5 and the strips 5, 3, 6, 2, and 3 cm long, respectively, for an A = 3 cm².

width's strips

With a cut made at a height of 4 cm from the base, the resulting area, painted red, is exactly equal to A cm². Your task is to find that heigth H and help Madruga.


There will be several test cases. The first line in each case begins with two integers N (1 ≤ N ≤ 105) and A (1 ≤ A ≤ 109) representing respectively the number of strips and the expected resulting area. The next line contains N integers, representing the length Ci (1 <= Ci <= 104) of each strip.

The input ends with A = C = 0, which should not be processed.


For each test case, output a single line, the height H of the cut that Madruga must do so that the sum of the area of the cut strips is equal to A cm². Print the answer with 4 decimal places.

Output ":D" if no cutting is required, or "-.-" if it’s impossible.

Input Sample Output Sample

5 3

5 3 6 2 3

4 14

2 5 2 5

0 0