{"problem":{"name":"Intervals","description":{"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, ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"cf16_exhibition_final_f"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $1 ≤ N ≤ 5000$\n*   $1 ≤ L_i, R_i ≤ 10^9$\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$L_1$ $R_1$\n:\n$L_N$ $R_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"cf16_exhibition_final_f","tags":[],"sample_group":[["4\n2 7\n2 5\n4 1\n7 5","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."],["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","7337"]],"created_at":"2026-03-03 11:01:14"}}