{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cbr\u003eThe 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\u0027ll have to find out whether this is a reasonable strategy or not.\u003cbr\u003eWe\u0027ll study a relatively simple mathematical model of a traffic jam. Assume that there\u0027s an \u003ci\u003eN\u003c/i\u003e-lane road, lanes numbered from 1 to \u003ci\u003eN\u003c/i\u003e, and \u003ci\u003ei\u003c/i\u003e\u003csup\u003e\u003ci\u003eth\u003c/i\u003e\u003c/sup\u003e lane is moving with speed \u003ci\u003eb\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e+\u003ci\u003ea\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e·\u003ci\u003esin\u003c/i\u003e(\u003ci\u003et\u003c/i\u003e+δ\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e) at the moment \u003ci\u003et\u003c/i\u003e. It is always true that \u003ci\u003eb\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u0026gt; \u003ci\u003ea\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, i.e., the speed of movement is always positive. You can change the lane you\u0027re in at any time, it takes \u003ci\u003ec\u003c/i\u003e·|x-\u003ci\u003ey\u003c/i\u003e| to change from \u003ci\u003ex\u003c/i\u003e\u003csup\u003e\u003ci\u003eth\u003c/i\u003e\u003c/sup\u003e lane to \u003ci\u003ey\u003c/i\u003e\u003csup\u003e\u003ci\u003eth\u003c/i\u003e\u003c/sup\u003e. We\u0027ll assume that you\u0027re not moving forward during that period.\u003cbr\u003eDetermine the time you need to travel the distance of \u003ci\u003ed\u003c/i\u003e, and the method of achieving that time. You\u0027re starting at the moment 0 at lane 1, you may finish at any lane.\u003cbr\u003e\u003cdiv align\u003d\"left\" style\u003d\"margin-top: 1.0em;\"\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/div\u003eThe first line of input contains two integers \u003ci\u003eN\u003c/i\u003e and \u003ci\u003ed\u003c/i\u003e and a floating-point number \u003ci\u003ec\u003c/i\u003e, 1 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 5, 1 ≤ \u003ci\u003ed\u003c/i\u003e ≤ 1000, 0.001 ≤ \u003ci\u003ec\u003c/i\u003e ≤ 1000. The next \u003ci\u003eN\u003c/i\u003e lines describe lanes, each containing two integers \u003ci\u003ea\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e and \u003ci\u003eb\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e and a floating-point number δ\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, 0 ≤ \u003ci\u003ea\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u0026lt; \u003ci\u003eb\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 100, 0 ≤δ\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u0026lt; 2π.\u003cbr\u003e\u003cdiv align\u003d\"left\" style\u003d\"margin-top: 1.0em;\"\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/div\u003eOn the first line of output print the minimal time required to travel the distance of \u003ci\u003ed\u003c/i\u003e. On the second line of output print the number \u003ci\u003eK\u003c/i\u003e of lane changes required to do that. \u003ci\u003eK\u003c/i\u003e should not be more than 10\u003csup\u003e6\u003c/sup\u003e, it is guaranteed that there always exists an optimal strategy requiring not more than 10\u003csup\u003e6\u003c/sup\u003e lane changes. On the next \u003ci\u003eK\u003c/i\u003e 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\u0027re many possible schedules, output any.\u003cbr\u003eOutput all the floating-point numbers with maximal precision possible. Your solution will be considered correct if verifying your schedule doesn\u0027t lead to discrepancies of more than 10\u003csup\u003e-6\u003c/sup\u003e (in checking the total distance traveled, in checking that lane changes are non-overlapping, etc), so it\u0027s better for you to output at least 10-12 digits after the decimal point in each floating-point number.\u003cbr\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 100 0.5\n4 5 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e19.71726232777025\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 100 0.5\n4 5 0\n2 5 0.5\n0 5 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e19.052103083697858\n4\n2 3.6645304897691258\n1 5.783185307179586\n2 9.947715796948712\n3 15.207963267948966\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}