P3051 [USACO12MAR] Haybale Restacking G

题目描述

一个环上有 $N$ 个位置。第 $i$ 个位置初始囤有 $A_i$ 捆干草，通过向相邻位置移动干草，使第 $i$ 个位置最后囤有 $B_i$ 捆干草。 保证 $\sum A_i$ 等于 $\sum B_i$ 。

干草必须沿相邻位置来移动，每移动一捆干草到一个相邻位置，要消耗约翰一单位的能量。

请计算最少消耗多少能量才能让所有位置的干草数量从 $A_i$ 变成 $B_i$ 。

由于是环，所以 $1$ 号位和 $N$ 号位也算作是相邻的。

输入格式

第一行一个正整数 $N$($1 \le N \le 10^5$).
下来 $N$ 行，每行两个整数 $A_i$ 和 $B_i$ ($1 \le A_i , B_i \le 1000$).

输出格式

一行一个整数，表示最小消耗的能量。

样例 #1

样例输入 #1

4 
7 1 
3 4 
9 2 
1 13

样例输出 #1

13

说明/提示

圆周上共有 $4$ 堆。初始时，各堆分别包含 $7$、$3$、$9$、$1$ 捆干草。约翰希望将其调整为各堆分别包含 $1$、$4$、$2$、$13$ 捆干草。

所需最小工作量为 $13$（从第 $1$ 堆移动 $6$ 捆到第 $4$ 堆，从第 $3$ 堆移动 $1$ 捆到第 $2$ 堆，从第 $3$ 堆再移动 $6$ 捆到第 $4$ 堆）。