{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cbr\u003eRon is a master of a ramen shop.\u003cbr\u003eRecently, he has noticed some customers wait for a long time. This has been caused by lack of seats during lunch time. Customers loses their satisfaction if they wait for a long time, and some of them will even give up waiting and go away. For this reason, he has decided to increase seats in his shop. To determine how many seats are appropriate, he has asked you, an excellent programmer, to write a simulator of customer behavior.\u003cbr\u003eCustomers come to his shop in groups, each of which is associated with the following four parameters: \u003cul\u003e \u003cli\u003e\u003ci\u003eT\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e: when the group comes to the shop \u003c/li\u003e\u003cli\u003e\u003ci\u003eP\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e: number of customers \u003c/li\u003e\u003cli\u003e\u003ci\u003eW\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e: how long the group can wait for their seats \u003c/li\u003e\u003cli\u003e\u003ci\u003eE\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e: how long the group takes for eating \u003c/li\u003e\u003c/ul\u003e\u003cbr\u003eThe \u003ci\u003ei\u003c/i\u003e-th group comes to the shop with \u003ci\u003eP\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e customers together at the time \u003ci\u003eT\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e. If \u003ci\u003eP\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e successive seats are available at that time, the group takes their seats immediately. Otherwise, they wait for such seats being available. When the group fails to take their seats within the time \u003ci\u003eW\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e (inclusive) from their coming and strictly before the closing time, they give up waiting and go away. In addition, if there are other groups waiting, the new group cannot take their seats until the earlier groups are taking seats or going away.\u003cbr\u003eThe shop has \u003ci\u003eN\u003c/i\u003e counters numbered uniquely from 1 to \u003ci\u003eN\u003c/i\u003e. The \u003ci\u003ei\u003c/i\u003e-th counter has \u003ci\u003eC\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e seats. A group cannot spread over multiple counters. The group prefers \"seats with a greater distance to the nearest group.\" Precisely, the group takes their seats according to the criteria listed below. For each block of seats of appropriate size within each counter, values \u003ci\u003eS\u003c/i\u003e\u003csub\u003e\u003ci\u003eL\u003c/i\u003e\u003c/sub\u003e and \u003ci\u003eS\u003c/i\u003e\u003csub\u003e\u003ci\u003eR\u003c/i\u003e\u003c/sub\u003e are calculated. Here, \u003ci\u003eS\u003c/i\u003e\u003csub\u003e\u003ci\u003eL\u003c/i\u003e\u003c/sub\u003e denotes the number of successive empty seats on the left side of the group after their seating, and \u003ci\u003eS\u003c/i\u003e\u003csub\u003e\u003ci\u003eR\u003c/i\u003e\u003c/sub\u003e the number on the right side. \u003ci\u003eS\u003c/i\u003e\u003csub\u003e\u003ci\u003eL\u003c/i\u003e\u003c/sub\u003e and \u003ci\u003eS\u003c/i\u003e\u003csub\u003e\u003ci\u003eR\u003c/i\u003e\u003c/sub\u003e are considered to be infinity if there are no other customers on the left side and on the right side respectively. Note that these numbers don\u0027t take into account people in other counters. \u003cli\u003ePrefers seats maximizing \u003ci\u003emin\u003c/i\u003e { \u003ci\u003eS\u003c/i\u003e\u003csub\u003e\u003ci\u003eL\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003eS\u003c/i\u003e\u003csub\u003e\u003ci\u003eR\u003c/i\u003e\u003c/sub\u003e }. \u003c/li\u003e\u003cli\u003eIf there are multiple alternatives meeting the first criterion, prefers seats maximizing \u003ci\u003emax\u003c/i\u003e { \u003ci\u003eS\u003c/i\u003e\u003csub\u003e\u003ci\u003eL\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003eS\u003c/i\u003e\u003csub\u003e\u003ci\u003eR\u003c/i\u003e\u003c/sub\u003e }. \u003c/li\u003e\u003cli\u003eIf there are still multiple alternatives, prefers the counter of the smallest number. \u003c/li\u003e\u003cli\u003eIf there are still multiple alternatives, prefers the leftmost seats. \u003cbr\u003eWhen multiple groups are leaving the shop at the same time and some other group is waiting for available seats, seat assignment for the waiting group should be made after all the finished groups leave the shop. If a customer starts eating, he is allowed to finish even after the shop closes.\u003cbr\u003eYour task is to calculate the average satisfaction over customers. The satisfaction of a customer in the \u003ci\u003ei\u003c/i\u003e-th group is given as follows: \u003cul\u003e \u003cli\u003eIf the group goes away without eating, -1. \u003c/li\u003e\u003cli\u003eOtherwise, (\u003ci\u003eW\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e - \u003ci\u003et\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e) / \u003ci\u003eW\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e where \u003ci\u003et\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e is the actual waiting time for the \u003ci\u003ei\u003c/i\u003e-th group (the value ranges between 0 to 1 inclusive). \u003c/li\u003e\u003c/ul\u003e\u003cbr\u003e\u003cdiv align\u003d\"left\" style\u003d\"margin-top: 1.0em;\"\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/div\u003eThe input has the following format:\u003cbr\u003e\u003ci\u003eN\u003c/i\u003e \u003ci\u003eM\u003c/i\u003e \u003ci\u003eT\u003c/i\u003e\u003cbr\u003e\u003ci\u003eC\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e \u003ci\u003eC\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e... \u003ci\u003eC\u003c/i\u003e\u003csub\u003e\u003ci\u003eN\u003c/i\u003e\u003c/sub\u003e\u003cbr\u003e\u003ci\u003eT\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e \u003ci\u003eP\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e \u003ci\u003eW\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e \u003ci\u003eE\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e\u003cbr\u003e\u003ci\u003eT\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e \u003ci\u003eP\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e \u003ci\u003eW\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e \u003ci\u003eE\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e\u003cbr\u003e...\u003cbr\u003e\u003ci\u003eT\u003c/i\u003e\u003csub\u003e\u003ci\u003eM\u003c/i\u003e\u003c/sub\u003e \u003ci\u003eP\u003c/i\u003e\u003csub\u003e\u003ci\u003eM\u003c/i\u003e\u003c/sub\u003e \u003ci\u003eW\u003c/i\u003e\u003csub\u003e\u003ci\u003eM\u003c/i\u003e\u003c/sub\u003e \u003ci\u003eE\u003c/i\u003e\u003csub\u003e\u003ci\u003eM\u003c/i\u003e\u003c/sub\u003e\u003cbr\u003e\u003ci\u003eN\u003c/i\u003e indicates the number of counters, \u003ci\u003eM\u003c/i\u003e indicates the number of groups and \u003ci\u003eT\u003c/i\u003e indicates the closing time. The shop always opens at the time 0. All input values are integers.\u003cbr\u003eYou can assume that 1 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 100, 1 ≤ \u003ci\u003eM\u003c/i\u003e ≤ 10000, 1 ≤ \u003ci\u003eT\u003c/i\u003e ≤ 10\u003csup\u003e9\u003c/sup\u003e, 1 ≤ \u003ci\u003eC\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 100, 0 ≤ \u003ci\u003eT\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e \u0026lt; \u003ci\u003eT\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e \u0026lt;... \u0026lt; \u003ci\u003eT\u003c/i\u003e\u003csub\u003e\u003ci\u003eM\u003c/i\u003e\u003c/sub\u003e \u0026lt; \u003ci\u003eT\u003c/i\u003e, 1 ≤ \u003ci\u003eP\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003emax\u003c/i\u003e{\u003ci\u003eC\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e}, 1 ≤ \u003ci\u003eW\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup\u003e9\u003c/sup\u003e and 1 ≤ \u003ci\u003eE\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup\u003e9\u003c/sup\u003e.\u003cbr\u003e\u003cdiv align\u003d\"left\" style\u003d\"margin-top: 1.0em;\"\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/div\u003eOutput the average satisfaction over all customers in a line. The output value may be printed with an arbitrary number of fractional digits, but may not contain an absolute error greater than 10\u003csup\u003e-9\u003c/sup\u003e.\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 4 100\n7\n10 1 50 50\n15 2 50 50\n25 1 50 50\n35 3 50 50\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0.7428571428571429\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\u003e1 2 100\n5\n30 3 20 50\n40 4 40 50\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0.4285714285714285\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 3","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 2 100\n5\n49 3 20 50\n60 4 50 30\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0.5542857142857143\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 4","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 2 100\n5\n50 3 20 50\n60 4 50 30\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-0.1428571428571428\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 5","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\u003e2 3 100\n4 2\n10 4 20 20\n30 2 20 20\n40 4 20 20\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0.8000000000000000\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}