[588A] Duff y la carne

Enlace a Codeforces

Duff es adicta a la carne! Malek quiere mantenerla feliz durante $n$ días. Y para ser feliz en cada i-ésimo día, ella necesita comer exactamente $a_i$ kilogramos de carne.

En la zona residencial del pueblo hay una gran tienda y Malek quiere comprar allí la carne para ella. Cada i-ésimo día, venden la carne a $p_i$ dólares por kilo. Malek conoce todos los números $a_1, \ldots, a_n$ y $p_1, \ldots, p_n$. Y cada día, puede comprar una cantidad arbitraria de carne, como también guardar algo de la carne que tiene para el futuro.

Malek está un poco cansado de tanto cocinar carne, así que pide tu ayuda. Ayúdalo a minimizar el dinero total que debe gastar para mantener feliz a Duff durante $n$ días.

Entrada

La primera línea contiene un entero $n$ ($1 \leq n \leq 10^5$), el número de días.

En las siguientes $n$ líneas, cada i-ésima línea contiene dos enteros $a_i$ y $p_i$ ($1 \leq a_i, p_i \leq 100$), la cantidad de carne que necesita Duff y el costo de la carne en ese día.

Salida

Imprime el mínimo dinero necesario para mantener a Duff feliz durante $n$ días.

Ejemplos

input:
3
1 3
2 2
3 1

output:
10

input:
3
1 3
2 1
3 2

output:
8

Nota:

En el primer ejemplo: Una forma óptima sería comprar 1 kg de carne el primer día, 2 kg el segundo día y 3 kg el tercer día.

En el segundo ejemplo: Una forma óptima sería comprar 1 kg el primer día y 5 kg el segundo día (la carne necesaria para el segundo y tercer día).