{"raw_statement":[{"iden":"statement","content":"Richard and Janet are going on their first date. Richard has offered to meet her at home with his bicycle and Janet tells him she will call when she is ready in $10$ to $20$ minutes. But Richard is an impatient person; while he could wait at home for Janet's signal, he might also leave early and travel around the neighbourhood for a bit, in order to minimise the time it takes him to reach her once she calls. Due to his impatience, once Richard is on his bicycle, he does not want to ride any slower than the legal speed limit, stop at intersections, or wait outside Janet's house (but he does not mind passing by Janet's house and returning to it later).\n\nGiven the directed graph representing the neighbourhood around Richard's and Janet's houses, Richard wants to devise a route around the neighbourhood (after an optional waiting period at his own house) which minimises the time that Janet has to wait in the worst case. He can travel for as long as he likes and visit each intersection as many times as he likes.\n\nJanet will call Richard as soon as she is ready, and at that point, Richard will take the shortest path to her that he can. Richard does not know exactly when Janet will be ready, but he knows it will be in somewhere between $a$ and $b$ minutes (not necessarily at a whole minute).\n\nIf Richard is passing through an intersection at the exact same instant Janet calls, the call is considered to happen before he chooses what to do at the intersection. For example, if he is passing by Janet's house at the moment she calls, he can immediately stop there and she does not have to wait for him at all.\n\nIt could happen that Janet never has to wait for $w$ minutes, but that she might have to wait for $w -epsilon$ minutes for arbitrarily small $epsilon > 0$, if she calls Richard at some inopportune moment (say, nanoseconds after he has left an intersection). In this case, we still define the worst-case waiting time to be $w$.\n\nThe input consists of: \n\nRichard's house is at intersection $1$ and Janet's house is at intersection $n$. It is guaranteed that it is possible to travel from Richard's house to Janet's house, and that it is possible to exit each intersection through at least one road, even if that road just loops back to the same intersection.\n\nOutput the time Janet has to wait in the worst case assuming she will be ready in at least $a$ minutes and at most $b$ minutes and Richard plans his route optimally.\n\nIt can be shown that the worst-case waiting time is always an integer.\n\n"},{"iden":"input","content":"The input consists of:   One line with two integers $a$, $b$ ($0 <= a <= b <= 10^(12)$), indicating that Janet will be ready in at least $a$ minutes and at most $b$ minutes.  One line with two integers $n$, $m$ ($2 <= n <= m <= 10^5$), the number of intersections and the number of roads in the neighbourhood. The intersections are numbered from $1$ to $n$.  $m$ lines, each with three integers $u$, $v$ and $t$ ($1 <= u, v <= n$, $1 <= t <= 10^6$), indicating that there is a one-way road from intersection $u$ to intersection $v$, and that it takes Richard exactly $t$ minutes to travel along this road. Richard's house is at intersection $1$ and Janet's house is at intersection $n$. It is guaranteed that it is possible to travel from Richard's house to Janet's house, and that it is possible to exit each intersection through at least one road, even if that road just loops back to the same intersection."},{"iden":"output","content":"Output the time Janet has to wait in the worst case assuming she will be ready in at least $a$ minutes and at most $b$ minutes and Richard plans his route optimally.It can be shown that the worst-case waiting time is always an integer."},{"iden":"examples","content":"Input10 20\n3 5\n1 3 7\n2 1 1\n2 3 2\n2 3 5\n3 2 4\nOutput6\nInput4 10\n5 7\n1 4 6\n4 5 5\n4 5 3\n5 5 30\n1 2 1\n2 3 1\n3 2 1\nOutput5\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of inhabitants.  \nLet $ d \\in \\mathbb{Z}^+ $ be the number of nights of gem splitting.  \nLet $ r \\in \\mathbb{Z}^+ $ with $ r \\leq n $.  \n\nInitially, each inhabitant has 1 gem: $ \\mathbf{g}^{(0)} = (1, 1, \\dots, 1) \\in \\mathbb{Z}^n $.  \n\nEach night, one gem is chosen uniformly at random among all current gems and splits into two (i.e., one gem is replaced by two, increasing the total count by 1).  \n\nAfter $ d $ nights, let $ \\mathbf{g}^{(d)} = (g_1, g_2, \\dots, g_n) \\in \\mathbb{Z}^n $ denote the random vector of gem counts per inhabitant, with $ \\sum_{i=1}^n g_i = n + d $.  \n\nLet $ a_1 \\geq a_2 \\geq \\dots \\geq a_n $ be the non-increasing ordering of $ \\mathbf{g}^{(d)} $.  \n\n**Constraints**  \n1. $ 1 \\leq n, d \\leq 500 $  \n2. $ 1 \\leq r \\leq n $  \n\n**Objective**  \nCompute the expected value:  \n$$\n\\mathbb{E}\\left[ \\sum_{i=1}^r a_i \\right]\n$$","simple_statement":"There are n people on an island. Each starts with 1 gem. Every night, one gem is chosen uniformly at random and splits into two. After d nights, find the expected total number of gems held by the r richest people.","has_page_source":false}