Se está construyendo un nuevo barco pirata. La nave tiene ~N~ mástiles (polos) divididos en segmentos de tamaño unitario: la altura de un mástil es igual al número de sus segmentos. Cada mástil está equipado con una serie de velas y cada vela encaja exactamente en un segmento. Las velas en un mástil se pueden distribuir arbitrariamente entre diferentes segmentos, pero cada segmento se puede ajustar como máximo con una vela.

Las diferentes configuraciones de las velas generan diferentes cantidades de empuje cuando se exponen al viento. Las velas frente a otras velas a la misma altura obtienen menos viento y contribuyen con menos empuje. Para cada vela definimos como ineficiencia como el número total de velas que están detrás de esta vela y en la misma altura. Tenga en cuenta que "delante" y "detrás" se relacionan con la orientación del barco: en la figura siguiente, "delante" significa a la izquierda, y "detrás" significa a la derecha.

La ineficiencia total de una configuración es la suma de las ineficiencias de todas las velas individuales.

Delante Atras

Esta nave tiene 6 mástiles, de alturas 3, 5, 4, 2, 4 y 3 desde el frente (lado izquierdo de la imagen) hacia atrás. Esta distribución de las velas da una ineficiencia total de 10. La ineficiencia individual de cada vela está escrita dentro de la vela.

Tarea

Escriba un programa que, dada la altura y el número de velas en cada uno de los ~N~ mástiles, determine la menor total ineficiencia posible.

Entrada

La primera línea de entrada contiene un número entero ~N (2 \le N \le 100 000)~, el número de mástiles en el barco.

Cada una de las siguientes ~N~ líneas contiene dos enteros ~H~ y ~K (1 \le H \le 100 000, 1 \le K \le H)~, la altura y el número de velas en el mástil correspondiente. Los mástiles se dan en orden de la parte delantera a la parte posterior de la nave.

Salida

La salida debe consistir en un solo entero, la menor ineficiencia total posible.

Nota: utilice un tipo entero de ~64 bits~ para calcular y generar el resultado (long long en C/C++, int64 en Pascal).

Ejemplo de Entrada

6
3 2
5 3
4 1
2 1
4 3
3 2

Ejemplo de Salida

18

Calificación

En casos de prueba con un total de ~25~ puntos, el número total de formas de organizar las velas será como máximo de ~1 000 000~.