FJ desea organizar sus pilas de heno en un círculo. Inicialmante, tiene N pilas con cantidades de heno dadas por B_i. Sin embargo, el conductor, que solo recordó el requisito de las N pilas en un círculo, registró las cantidades como A_i. La suma total de A_i es igual a la suma total de B_i.

FJ puede mover heno entre pilas. El costo de mover una unidad de heno x pasos es x. La distancia entre pilas adyacentes es 1. El objetivo es calcular el mínimo costo de energía para que la cantidad de heno en cada pila cumpla con el requisito B_i, es decir, A_i = B_i para todo i.

Entrada

La primera línea contiene un entero N (1 <= N <= 100,000).

Las siguientes N líneas contienen dos enteros cada una. La línea i+1 describe A_i y B_i (1 <= A_i, B_i <= 1000).

Salida

Imprimir un número que represente el costo mínimo de energía.

Ejemplo

Entrada:

4
7 1
3 4
9 2
1 13

Salida:

13

Análisis

Sea x_i la cantidad de heno movida de la pila i a la pila i+1 (con i+1 siendo 1 si i=N). Si x_i es positivo, representa heno movido en sentido horario; si es negativo, representa heno movido en sentido antihorario.

La conservación del heno en cada pila se puede expresar como:

• Pila 1: A_1 - x_1 + x_N = B_1
• Pila 2: A_2 - x_2 + x_1 = B_2
• ...
• Pila N: A_N - x_N + x_{N-1} = B_N

Reordenando las ecuaciones:

• x_1 - x_N = A_1 - B_1
• x_2 - x_1 = A_2 - B_2
• ...
• x_N - x_{N-1} = A_N - B_N

Sea d_i = A_i - B_i. Entonces:

• x_1 - x_N = d_1
• x_2 - x_1 = d_2
• ...
• x_N - x_{N-1} = d_N

Definimos la diferencia acumulada c_i como c_i = x_i - x_N.

• c_1 = x_1 - x_N = d_1
• c_2 = x_2 - x_N = (x_2 - x_1) + (x_1 - x_N) = d_2 + d_1
• c_3 = x_3 - x_N = (x_3 - x_2) + (x_2 - x_N) = d_3 + c_2 = d_3 + d_2 + d_1
• ...
• c_i = sum(d_j for j from 1 to i)

El objetivo es minimizar el costo total, que es la suma de las distancias absolutas de los movimientos: sum(|x_i|).

De las ecuaciones, tenemos x_i = c_i + x_N.

El costo total se convierte en: sum(|c_i + x_N|).

Esto es un problema clásico de minimizar la suma de distancias aboslutas a un punto. La solución óptima para x_N es la mediana de los valores -c_i.

Calculamos las diferenncias acumuladas c_i y luego encontramos la mediana de -c_i. El costo mínimo es la suma de las distancias absolutas de cada c_i a la mediana encontrada.

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>

int main() {
   std::ios_base::sync_with_stdio(false);
   std::cin.tie(NULL);
   int n;
   std::cin >> n;
   std::vector<long long> diff_prefix_sum(n + 1, 0);
   for (int i = 0; i < n; ++i) {
       int a, b;
       std::cin >> a >> b;
       diff_prefix_sum[i + 1] = diff_prefix_sum[i] + (a - b);
   }

   // We need to find x_N that minimizes sum(|c_i + x_N|)
   // where c_i = diff_prefix_sum[i].
   // This is equivalent to minimizing sum(|diff_prefix_sum[i] - (-x_N)|).
   // The optimal value for -x_N is the median of diff_prefix_sum[1...N].

   // Extract the relevant prefix sums (c_1 to c_N)
   std::vector<long long> c_values(diff_prefix_sum.begin() + 1, diff_prefix_sum.end());

   // Sort to find the median
   std::sort(c_values.begin(), c_values.end());

   // The median is at index n/2 for 0-based indexing
   long long median_c = c_values[n / 2];

   // The optimal value for -x_N is the median of c_i.
   // Let optimal_neg_xN = median_c.
   // Then the optimal x_N = -median_c.
   // The cost is sum(|c_i + x_N|) = sum(|c_i - median_c|)

   long long min_cost = 0;
   for (long long val : c_values) {
       min_cost += std::abs(val - median_c);
   }

   std::cout << min_cost << std::endl;

   return 0;
}