题目描述

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

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

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

输入格式

输入第一行，一个正整数

n 表示列车车厢数 接下来

n行，每行两个整数

a [i] ​ ,b [i] ​ 分别表示每节车厢内男女人数。

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

数据范围

对于 30 % 的数据，

1≤n≤10

对于 60 % 的数据，

1≤n≤100， 1≤a [i] ​ ,b [i] ​ ≤1000

对于 100 % 的数据，

1≤n≤5000，

1≤a [i] ​ ,b [i] ​ ≤10 的9次方