問題文

狼と狐が健康診断を行うことになりました。健康診断は $N$ 日間にわたって行われ、それぞれの狼と狐は、$N$ 日間のうちある $1$ 日に健康診断に参加することになっています。 $i$ 日目に健康診断に参加したい狼は $w_i$ 匹、$i$ 日目に健康診断に参加したい狐は $f_i$ 匹います。

ただし、$N$ 日間のそれぞれの日において、狼または狐のいずれか一方しか診断できないことになっています。 希望が合わない場合は他の日に参加することになるが、$i$ 日目に健康診断に参加したい狼や狐が $j$ 日目に健康診断を行う場合、不満度は $|i-j|$ です。 健康診断を行える日が存在しないときは、不満度は $10^{100}$ です。それぞれの狼と狐は、参加できる中で不満度が最小になるような日に健康診断に参加します。

$N$ 日間のそれぞれの日において、狼と狐いずれを診断するかを最適に決めた時の、全ての狼と狐の不満度の合計の最小値を求めてください。

制約

• $2 ≤ N ≤ 3000$
• $0 ≤ w_i, f_i ≤ 10^9$

入力例 1Copy

6
1 5
1 3
3 4
3 2
5 1
6 2

出力例 1Copy

15

$3,5,6$ 日目に狼を診断し、$1,2,4$ 日目に狐を診断するのが最適です。

入力例 2Copy

10
26 37
1 49
1 74
2 99
2 100
2 75
3 62
3 62
2 37
2 37

出力例 2Copy

108