Need for Speed

Given segment distances and speedometer readings plus a total time, find the constant offset c making the summed travel times equal t.

Medium4Binary searchMathImplementationInterviewNo attempts yetTime limit1sMemory limit512 MB

Problem

Sheila is a student and she drives a typical student car: old, slow, rusty, and falling apart. Recently the needle on the speedometer fell off. She glued it back on, but she might have placed it at the wrong angle. So when the speedometer reads ss, her true speed is s+cs + c, where cc is an unknown constant that may be negative.

Sheila kept a careful record of a recent journey and wants to use it to compute cc. The journey consisted of nn segments. In the iith segment she traveled a distance of did_i, and the speedometer read sis_i for that entire segment. The whole journey took time tt. Help Sheila by computing cc.

The speedometer may show a negative reading, but her true speed was greater than zero on every segment.

Input

The first line contains two integers nn and tt. Here nn is the number of segments of the journey (1n10001 \le n \le 1000), and tt is the total time of the journey (1t1061 \le t \le 10^6).

Each of the next nn lines describes one segment. The iith of these lines contains two integers did_i and sis_i (1di10001 \le d_i \le 1000, si1000|s_i| \le 1000), the distance and the speedometer reading for the iith segment. Time is given in hours, distance in miles, and speed in miles per hour.

A real number cc that makes every true speed greater than zero and the total time exactly tt always exists. The sum i=1ndisi+c\sum_{i=1}^{n} \frac{d_i}{s_i + c} strictly decreases in cc, so that value is unique.

Output

Print the constant cc in miles per hour, rounded to exactly six digits after the decimal point. If the value is zero, print 0.000000 and not -0.000000.