331. Traffic Jam
Time limit per test: 0.25
second(s)
Memory limit: 65536
kilobytes
input: standard
output: standard
The most annoying thing in Moscow traffic jams is that drivers constantly try to suddenly change lanes in order to move faster. In this problem you'll have to find out whether this is a reasonable strategy or not.
We'll study a relatively simple mathematical model of a traffic jam. Assume that there's an
Nlane road, lanes numbered from 1 to
N, and
i^{th} lane is moving with speed
b_{i}+
a_{i}·
sin(
t+δ
_{i}) at the moment
t. It is always true that
b_{i} >
a_{i}, i.e., the speed of movement is always positive. You can change the lane you're in at any time, it takes
c·x
y to change from
x^{th} lane to
y^{th}. We'll assume that you're not moving forward during that period.
Determine the time you need to travel the distance of
d, and the method of achieving that time. You're starting at the moment 0 at lane 1, you may finish at any lane.
Input
The first line of input contains two integers
N and
d and a floatingpoint number
c, 1 ≤
N ≤ 5, 1 ≤
d ≤ 1000, 0.001 ≤
c ≤ 1000. The next
N lines describe lanes, each containing two integers
a_{i} and
b_{i} and a floatingpoint number δ
_{i}, 0 ≤
a_{i} <
b_{i} ≤ 100, 0 ≤δ
_{i} < 2π.
Output
On the first line of output print the minimal time required to travel the distance of
d. On the second line of output print the number
K of lane changes required to do that.
K should not be more than 10
^{6}, it is guaranteed that there always exists an optimal strategy requiring not more than 10
^{6} lane changes. On the next
K lines print the changes themselves, each line should contain the new lane number and the time when the change is started. The changes should be printed in chronological order. If there're many possible schedules, output any.
Output all the floatingpoint numbers with maximal precision possible. Your solution will be considered correct if verifying your schedule doesn't lead to discrepancies of more than 10
^{6} (in checking the total distance traveled, in checking that lane changes are nonoverlapping, etc), so it's better for you to output at least 1012 digits after the decimal point in each floatingpoint number.
Example(s)
sample input

sample output

1 100 0.5
4 5 0

19.71726232777025
0

sample input

sample output

3 100 0.5
4 5 0
2 5 0.5
0 5 0

19.052103083697858
4
2 3.6645304897691258
1 5.783185307179586
2 9.947715796948712
3 15.207963267948966
