{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThen came the long-awaited birthday. Only one test left - fi\u001cnd a way to Ira\u0027s home.\u003c/p\u003e\n\n\u003cp\u003eThe most popular form of transport in the city are buses. Each bus has two drivers, one of them knows one route, and the other - other route. However the time and place of start are the same for both bus drivers. Each day one of the drivers is working, and the other is resting. If Alex is on a bus stop, he will immediately know which drivers are now working on buses departing from this stop. However, before he reaches the stop, he only knows the schedule of possible movement of buses and the probabllity that the \u001crst driver works today. Sasha lives near a bus stop with number \u003cstrong\u003e1\u003c/strong\u003e and can be on it at any time, and Ira lives near to the stop \u003cstrong\u003eN\u003c/strong\u003e. Find the average arrival time for Sasha. At the same time Sasha would never use a way that could cause not reaching Ira\u0027s home at all, but among all the other he chooses the one that minimizes the expected time of arrival.\u003c/p\u003e\n\n\u003cp\u003eImportant facts:\u003c/p\u003e\n\n\u003cul\u003e\n\u003cp\u003e\u003cli\u003e Network trafi\u001ec of buses is an acyclic directed graph.\u003c/p\u003e\n\n\u003cp\u003e\u003cli\u003e You can instantly change from one bus to another one.\u003c/p\u003e\n\n\u003cp\u003e\u003cli\u003e In determining the optimal strategy Sasha also counts that on arrival at each stop, he gets the informations about today\u0027s drivers.\u003c/p\u003e\n\n\u003cp\u003e\u003cli\u003e Initially, Sasha doesn\u0027t know extra information even about his stop.\u003c/p\u003e\n\n\u003c/ul\u003e\n\n\u003cp\u003e\u003ch2\u003eInput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003eIn the fi\u001crst row are given two integers \u003cstrong\u003eN\u003c/strong\u003e and \u003cstrong\u003eK\u003c/strong\u003e (\u003cstrong\u003e2\u003c/strong\u003e ≤ \u003cstrong\u003eN\u003c/strong\u003e ≤ \u003cstrong\u003e10^5\u003c/strong\u003e, \u003cstrong\u003e0\u003c/strong\u003e ≤ \u003cstrong\u003eK\u003c/strong\u003e ≤ \u003cstrong\u003e10^5\u003c/strong\u003e) --- the number of stops and buses. In each of the next \u003cstrong\u003eK\u003c/strong\u003e lines information about buses is described: seven integers \u003cstrong\u003eu d p v_1 a_1 v_2 a_2\u003c/strong\u003e (\u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003eu\u003c/strong\u003e, \u003cstrong\u003ev_1\u003c/strong\u003e, \u003cstrong\u003ev_2\u003c/strong\u003e ≤ \u003cstrong\u003eN\u003c/strong\u003e, \u003cstrong\u003eu\u003c/strong\u003e ≠ \u003cstrong\u003ev_1\u003c/strong\u003e, \u003cstrong\u003eu\u003c/strong\u003e ≠ \u003cstrong\u003ev_2\u003c/strong\u003e, \u003cstrong\u003e0\u003c/strong\u003e ≤ \u003cstrong\u003ed\u003c/strong\u003e, \u003cstrong\u003ea_1\u003c/strong\u003e, \u003cstrong\u003ea_2\u003c/strong\u003e ≤ \u003cstrong\u003e1440\u003c/strong\u003e, \u003cstrong\u003ed\u003c/strong\u003e \u003c \u003cstrong\u003ea_1\u003c/strong\u003e, \u003cstrong\u003ed\u003c/strong\u003e \u003c \u003cstrong\u003ea_2\u003c/strong\u003e, \u003cstrong\u003e0\u003c/strong\u003e \u003c \u003cstrong\u003ep\u003c/strong\u003e \u003c \u003cstrong\u003e100\u003c/strong\u003e) --- number of stops and time of departure, the probability that the \u001crst driver works, place and time of arrival, for fi\u001crst and for second driver, respectively.\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eOutput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003ePrint average arrival time to \u003cstrong\u003eN\u003c/strong\u003e\u0027th stop for Sasha with an absolute or a relative error of \u003cstrong\u003e10^\\{-6\\\u003c/strong\u003e}, or \u003cstrong\u003e-1\u003c/strong\u003e, if there is a nonzero probability of not getting there at all.\u003c/p\u003e\n\n"}},{"title":"Example","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\u003e5 6\n1 60 50 2 200 3 150\n1 100 25 2 160 3 150\n1 200 50 5 350 4 300\n2 180 50 5 300 4 280\n3 400 80 5 600 5 660\n4 350 50 5 500 5 550\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e423.4375000000000\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}