{"raw_statement":[{"iden":"statement","content":"A well-known programming contest is considering a new way to position its teams. For the contest all $n$ teams have to be assigned some position $(x, y)$ in an infinitely-large gym hall. To keep a good overview of the teams the following strategy is chosen:\n\nAll teams have been assigned a unique integer ID in the range $[ 1, n ]$. Any two teams with IDs $i$ and $j$, where $i < j$, must be placed at positions $(x_i, y_i)$, $(x_j, y_j)$, such that $x_i <= x_j$ and $y_i <= y_j$.\n\nUnfortunately, someone already assigned the (fixed) internet access point for each team. The access points are quite big and only have one port, so access points for different teams are located at different positions. Every team must be connected to its designated access point by a direct UTP cable. The cost of a UTP cable of length $ell$ is $ell^2$.\n\nFind a placement for all teams, such that their respective order along both axes is maintained and the total cost of the required UTP cables is minimised. As the judges are not too worried about privacy, they are fine with two (or more) teams being placed at the exact same location or being arbitrarily close together. See the figure for an example.\n\nOutput the minimum total cost of all UTP cables required to connect the teams to their access points in an optimal legal layout.\n\nYour answer should have an absolute or relative error of at most $10^(-6)$.\n\n"},{"iden":"input","content":"  One line with one integer $n$ ($1 <= n <= 10^5$), the number of teams.  $n$ lines, the $i$th of which contains two integers $s_i$, $t_i$ ($1 <= s_i, t_i <= 10^6$), the location of the internet access point of team $i$. "},{"iden":"output","content":"Output the minimum total cost of all UTP cables required to connect the teams to their access points in an optimal legal layout.Your answer should have an absolute or relative error of at most $10^(-6)$."},{"iden":"examples","content":"Input6\n11 6\n23 7\n24 11\n24 32\n27 38\n42 42\nOutput0.000000000\nInput6\n4 1\n2 4\n3 2\n8 3\n5 6\n2 5\nOutput22.500000000\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ m \\in \\mathbb{Z}^+ $ be the number of buses, $ n \\in \\mathbb{Z}^+ $ the number of stations, and $ k \\in \\mathbb{Z}^+ $ the deadline to reach station 1.  \nLet $ B = \\{ (a_i, b_i, s_i, t_i, p_i) \\mid i \\in \\{1, \\dots, m\\} \\} $ be the set of buses, where:  \n- $ a_i, b_i \\in \\{0, 1, \\dots, n-1\\} $, $ a_i \\ne b_i $: start and destination stations,  \n- $ s_i, t_i \\in \\mathbb{Z} $: departure and arrival times, with $ 0 \\le s_i < t_i < k $,  \n- $ p_i \\in [0,1] $: probability bus $ i $ operates (independent events).  \n\n**Constraints**  \n1. $ 1 \\le m \\le 10^6 $, $ 2 \\le n \\le 10^6 $, $ 1 \\le k \\le 10^{18} $  \n2. For all buses: $ 0 \\le s_i < t_i < k $, $ 0 \\le p_i \\le 1 $, with at most 10 decimal digits.  \n3. You start at station 0 at time 0.  \n4. You may only board a bus $ i $ if you arrive at station $ a_i $ at time $ \\tau $ with $ \\tau < s_i $.  \n5. At any station, if multiple buses depart at the same time $ s $, you may attempt at most one.  \n6. You cannot wait beyond time $ k $; arriving at station 1 at or before time $ k $ is a success.  \n\n**Objective**  \nCompute the maximum probability $ P $ of reaching station 1 by time $ k $, under optimal decision-making, where decisions are adaptive and based on observed bus operations (but not future ones).  \n\nLet $ f(\\tau, v) $ be the maximum probability of reaching station 1 by time $ k $, starting from station $ v \\in \\{0, \\dots, n-1\\} $ at time $ \\tau \\in [0, k) $.  \nThen:  \n$$\nf(\\tau, 1) = 1 \\quad \\text{for all } \\tau \\le k\n$$\n$$\nf(\\tau, v) = \\max_{\\substack{i: a_i = v \\\\ s_i > \\tau}} \\left\\{ p_i \\cdot f(t_i, b_i) + (1 - p_i) \\cdot f(\\tau, v) \\right\\} \\quad \\text{for } v \\ne 1\n$$\nwith the understanding that if no bus is available, $ f(\\tau, v) = 0 $ if $ v \\ne 1 $.  \n\nSolve for $ f(0, 0) $.","simple_statement":"You are at station 0 and need to reach station 1 (airport) by time k using buses. Each bus has a start station, end station, departure time, arrival time, and a probability it will run. You can only board a bus if you arrive at its station strictly before it departs. If multiple buses leave at the same time, you can try only one. You want the maximum probability of reaching the airport on time.","has_page_source":false}