该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

J 原来有 n 堆木头，每堆有 a[i]根木头。现在 J 把这 n 堆木头按环形放置，但 J 觉得这不够美观，于是希望每堆的木头数为 b[i]。但运 1 根木头从第 j 堆到第 k 堆需要的费用是 j,k 环上的最短距离(即 min{|j-k|,|j+k-n|})。J 希望知 道完成这项操作的最小费用是多少

Format

Input

第一行一个整数 n 接下来 n 行，每行两个数 a[i],b[i]

Output

一行一个数表示最小费用

Samples

4
7 1
3 4
9 2
1 13

13

Limitation

其中一种最优方案：第 1 堆向第 2 堆运 1 根，第 1 堆向第 4 堆运 5 根，第 3堆向第 4 堆运 7 根 当然还存在另一种最优方案 30%的数据 n≤300 60%的数据 n≤10000 100%的数据 n≤100000