401. Geologist Dubrovsky
Time limit per test: 0.5
second(s)
Memory limit: 65536
kilobytes
input: standard
output: standard
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
ith river is
v_{i} meters per second and its width is
w_{i} meters.
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 seconds left?
Remember that his destination point is a point on the right bank of the easternmost river.
Input
The first line of the input contains three integer numbers
N,
u and
t
(1 ≤
N ≤ 50; 1 ≤
u,
t ≤ 1000).
Each of the following
N lines contains a pair of integers
w_{i},
v_{i}
(1 ≤
w_{i},
v_{i} ≤ 1000) describing corresponding parameters of the
ith river.
Output
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 seconds.
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
t_{1},
t_{2},...,
t_{N}, where
t_{i} is the time spent crossing the
river
i 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
original position.
Example(s)
sample input

sample output

1 1 1
1 1

1.4142135624
1.0000000000

sample input

sample output

2 1 6
1 1
2 1

11.5911099155
2.0000000000 4.0000000000
