Intervals

AtCoder

IDcf16_exhibition_final_f

Time2000ms

Memory256MB

Difficulty—

#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. Snuke 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]$. He 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. Compute the minimum cost required to achieve his goal. ## Constraints * $1 ≤ N ≤ 5000$ * $1 ≤ L_i, R_i ≤ 10^9$ * All values in the input are integers. ## Input The input is given from Standard Input in the following format: $N$ $L_1$ $R_1$ : $L_N$ $R_N$ [samples]

Samples

Input #1

Output #1

22

One optimal solution is as follows:

*   Move the interval $[-2, 7]$ to $[6, 15]$ with $8$ dollars
*   Move the interval $[-2, 5]$ to $[-1, 6]$ with $1$ dollars
*   Move the interval $[-4, 1]$ to $[-6, -1]$ with $2$ dollars
*   Move the interval $[-7, 5]$ to $[-18, -6]$ with $11$ dollars

The total cost is $8 + 1 + 2 + 11 = 22$ dollars.

Input #2

Output #2

API Response (JSON)

{
  "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, ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments