Velas
Se está construyendo un nuevo barco pirata. La nave tiene 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 mástiles, determine la menor total ineficiencia posible.
Entrada
La primera línea de entrada contiene un número entero , el número de mástiles en el barco.
Cada una de las siguientes líneas contiene dos enteros y , 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 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 puntos, el número total de formas de organizar las velas será como máximo de .
Comments