401. Geologist Dubrovsky
Time limit per test: 0.5
Memory limit: 65536
Geologist Dubrovsky travels a lot around the world and often faces different unusual phenomena.
And now he found a unique place on the planet, where N
rivers flow in parallel tight next to each other.
The distance between each pair of neighbouring rivers can be neglected. Rivers flow from the south to the north.
Geologist stays on the left bank of the most western river and wants to get to the right bank of the most eastern river.
The flow speed of i
-th river is vi
meters per second and its width is wi
Geologist Dubrovsky swims with the speed u
meters per second in still water.
If he swims across river, his real speed is a vector sum of his own speed vector and the speed
vector of the river flow.
What is the maximal distance Dubrovsky can get from his original position by the time of sunset,
if he has only t
Remember that his destination point is a point on the right bank of the easternmost river.
The first line of the input contains three integer numbers N
(1 ≤ N
≤ 50; 1 ≤ u
Each of the following N
lines contains a pair of integers wi
(1 ≤ wi
≤ 1000) describing corresponding parameters of the i
To the first line of the output write the desired distance or -1 if geologist can't
reach the right bank of the most eastern river in t
The distance with a relative or absolute error of at most 10-6
will be considered correct.
If solution exists the second line of the output should contain
the sequence t1
, where ti
is the time spent crossing the
in the case of optimal track. The track is optimal if as a result Dubrovsky gets
to the point on the right bank of the easternmost river, which is the farthest from his
1 1 1
2 1 6