{"raw_statement":[{"iden":"problem statement","content":"#nck { width: 30px; height: auto; }Snuke received $N$ intervals as a birthday present. The $i$\\-th interval was $[-L_i, R_i]$. It is guaranteed that both $L_i$ and $R_i$ are positive. In other words, the origin is strictly inside each interval.\nSnuke doesn't like overlapping intervals, so he decided to move some intervals. For any positive integer $d$, if he pays $d$ dollars, he can choose one of the intervals and move it by the distance of $d$. That is, if the chosen segment is $[a, b]$, he can change it to either $[a+d, b+d]$ or $[a-d, b-d]$.\nHe can repeat this type of operation arbitrary number of times. After the operations, the intervals must be pairwise disjoint (however, they may touch at a point). Formally, for any two intervals, the length of the intersection must be zero.\nCompute the minimum cost required to achieve his goal."},{"iden":"constraints","content":"*   $1 ≤ N ≤ 5000$\n*   $1 ≤ L_i, R_i ≤ 10^9$\n*   All values in the input are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$L_1$ $R_1$\n:\n$L_N$ $R_N$"},{"iden":"sample input 1","content":"4\n2 7\n2 5\n4 1\n7 5"},{"iden":"sample output 1","content":"22\n\nOne optimal solution is as follows:\n\n*   Move the interval $[-2, 7]$ to $[6, 15]$ with $8$ dollars\n*   Move the interval $[-2, 5]$ to $[-1, 6]$ with $1$ dollars\n*   Move the interval $[-4, 1]$ to $[-6, -1]$ with $2$ dollars\n*   Move the interval $[-7, 5]$ to $[-18, -6]$ with $11$ dollars\n\nThe total cost is $8 + 1 + 2 + 11 = 22$ dollars."},{"iden":"sample input 2","content":"20\n97 2\n75 25\n82 84\n17 56\n32 2\n28 37\n57 39\n18 11\n79 6\n40 68\n68 16\n40 63\n93 49\n91 10\n55 68\n31 80\n57 18\n34 28\n76 55\n21 80"},{"iden":"sample output 2","content":"7337"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}