Фермер Джон заказал большое количество пакетов с сеном. Он хочет разложить их в N кучек (1 <= N <= 100,000), расположенных по кругу, где куча i содержит Bi пакетов с сеном. Водитель грузовика разложил пакеты в N куч с Ai пакетов в каждой. Известно, что сумма Bi равна сумме Ai.
ФД хочет переместить кучи из их текущего положения Ai в требуемое BI. X единиц работы требуется, чтобы переместить один пакет из кучи в другую, которая отстоит на X шагов от данной по кругу.
Определите минимальное количество работы, требуемое для преобразования "хаоса" в "порядок". PROBLEM NAME: restack
Формат входных данных
* Строка 1: Одно целое число N.
* Строки 2..1+N: Строка i+1 содержит два целых числа Ai и Bi (1 <= Ai, Bi <= 1000).
Формат выходных данных
Примечание
Минимальное количество работы, которое надо совершить, равно 13: переместить 6 пакетов из кучи 1 в кучу 4, переместить 1 пакет из кучи 3 в кучу 2, переместить 6 пакетов из кучи 3 в кучу 4.