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 i-th river is vi meters per second and its width is wi 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 wi, vi (1 ≤ wi, vi ≤ 1000) describing corresponding parameters of the i-th 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 t1, t2,..., tN, where ti 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


Online Contester Team © 2002 - 2010. All rights reserved.