题目描述

有一列 $n$ 节车厢的高铁列车，每节车厢都有一个卫生间。现在已知下一趟列车运行时，第 $i$ 节车厢中，会有 $a_i$ 位男性乘客、 $b_i$ 位女性乘客。

现在，你可以将每节车厢的卫生间标识、标识成男卫生间或女卫生间中的一个，请问如何标识，才能使每位乘客到离自己最近的对应卫生间的距离之和最小？

乘客需要移动的距离，定义为对应卫生间所在车厢号与其自己所在车厢号的差值的绝对值，且全车必须至少有两种卫生间各一个。

输入格式

输入第一行，一个正整数 $n$ 表示列车车厢数 接下来$n$行，每行两个整数 $a_i,b_i$ 分别表示每节车厢内男女人数。

输出格式

输出一个整数，表示答案。

2
8 3
2 6

5

样例解释 1

第一节车厢设置成男卫生间，第二节车厢设置成女卫生间。 第一节车厢的3位女性乘客要走一个单位距离去第二节车厢，第二节车厢的2位男性性乘客要走一个单位距离去第一节车厢

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 10$
• 对于 $60\%$ 的数据，$1\leq n\leq 100$，$1 \leq a_i,b_i \leq 10^3$
• 对于 $100\%$ 的数据，$1\leq n\leq 5000$，$1 \leq a_i,b_i \leq 10^9$