Problem:
 Score : 1000 points    Problem Statement  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       Output Print the minimum cost required to achieve his goal.        Sample Input 1 4
2 7
2 5
4 1
7 5      Sample 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.       Sample Input 2 20
97 2
75 25
82 84
17 56
32 2
28 37
57 39
18 11
79 6
40 68
68 16
40 63
93 49
91 10
55 68
31 80
57 18
34 28
76 55
21 80      Sample Output 2 7337

Solution (Python):
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

import numpy as np

N = int(readline())
LR = [tuple(int(x) for x in line.split()) for line in readlines()]

"""
・奇数個のとき：中央にどれかを固定。
・偶数のとき：原点で左右に分けるとしてよい。
・基本的に長さで内側から昇順（奇数のときの中央は謎）。→ソートしてdpできる。
・左に置いた個数をもってdp更新。また、中央を使ったかも同時に持って。
・偶数のときは、中央に1つ置いた状態から始める。
・大きい区間から外側に入れていく。
"""

LR.sort(key = lambda x: -x[1]-x[0])

INF = 10**18
dp_0 = np.full(1,INF,np.int64) 
dp_1 = np.full(1,INF,np.int64) 
if N&1:
    dp_0[0] = 0
else:
    dp_1[0] = 0
for n,(L,R) in enumerate(LR):
    length = R + L
    prev_0 = dp_0
    prev_1 = dp_1
    dp_0 = np.full(n+2,INF,np.int64)
    dp_1 = np.full(n+2,INF,np.int64)
    x = np.arange(n+1,dtype=np.int64) 
    
    np.minimum(prev_0[:n+1] + R + x * length, dp_0[1:n+2], out=dp_0[1:n+2])
    np.minimum(prev_1[:n+1] + R + x * length, dp_1[1:n+2], out=dp_1[1:n+2])
    
    np.minimum(prev_0[:n+1] + L + (n-x) * length, dp_0[:n+1], out=dp_0[:n+1])
    np.minimum(prev_1[:n+1] + L + (n-x) * length, dp_1[:n+1], out=dp_1[:n+1])
    
    np.minimum(prev_0[:n+1] + (N-1)//2 * length, dp_1[:n+1], out = dp_1[:n+1])

answer = dp_1[N//2]
print(answer)

Solution (Python):
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

import numpy as np

N = int(readline())
LR = [tuple(int(x) for x in line.split()) for line in readlines()]

"""
・奇数個のとき：中央にどれかを固定。
・偶数のとき：原点で左右に分けるとしてよい。
・基本的に長さで内側から昇順（奇数のときの中央は謎）。→ソートしてdpできる。
・左に置いた個数をもってdp更新。また、中央を使ったかも同時に持って。
・偶数のときは、中央に1つ置いた状態から始める。
・大きい区間から外側に入れていく。
"""

LR.sort(key = lambda x: -x[1]-x[0])

INF = 10**18
dp_0 = np.full(N+1,INF,np.int64) 
dp_1 = np.full(N+1,INF,np.int64) 
if N&1:
    dp_0[0] = 0
else:
    dp_1[0] = 0
for n,(L,R) in enumerate(LR):
    length = R + L
    prev_0 = dp_0
    prev_1 = dp_1
    dp_0 = np.full(N+1,INF,np.int64)
    dp_1 = np.full(N+1,INF,np.int64)
    x = np.arange(n+1,dtype=np.int64) 
    
    np.minimum(prev_0[:n+1] + R + x * length, dp_0[1:n+2], out=dp_0[1:n+2])
    np.minimum(prev_1[:n+1] + R + x * length, dp_1[1:n+2], out=dp_1[1:n+2])
    
    np.minimum(prev_0[:n+1] + L + (n-x) * length, dp_0[:n+1], out=dp_0[:n+1])
    np.minimum(prev_1[:n+1] + L + (n-x) * length, dp_1[:n+1], out=dp_1[:n+1])
    
    np.minimum(prev_0[:n+1] + (N-1)//2 * length, dp_1[:n+1], out = dp_1[:n+1])

answer = dp_1[N//2]
print(answer)