Robert es el dueño de una cadena de producción con ~N~ fábricas ubicadas en línea recta a lo largo de una carretera. La fábrica ~i~ está en la posición ~x_i~ (medida en kilómetros desde el origen) y produce ~p_i~ unidades de producto por día.

Robert necesita construir almacenes en algunas de las fábricas para almacenar la producción. Un almacén en la fábrica ~i~ recibe la producción de todas las fábricas ~j \leq i~ que no tienen un almacén más cercano. El costo de construir un almacén en la fábrica ~i~ es ~c_i~ monedas.

El costo de transportar la producción desde la fábrica ~j~ hasta el almacén en la fábrica ~i~ es ~p_j * (x_i - x_j)~ monedas (o sea distancia por producción). La producción de cada fábrica debe enviarse exactamente a un almacén.

Robert debe decidir en qué fábricas construir almacenes para minimizar el costo total, que es la suma de los costos de construcción de los almacenes más los costos de transporte de todas las fábricas hasta sus respectivos almacenes.

Siempre se construye un almacén en la última fábrica.

Entrada

• La primera línea contiene un entero ~N~ , el número de fábricas.
• Las siguientes ~N~ líneas contienen tres enteros cada una: ~x_i, p_i~ y ~c_i~ ,la posición, la producción y el costo de construir un almacén en la fábrica ~i~. Se garantiza que las posiciones están estrictamente ordenadas: ~x_1 < x_2 < ... < x_N~.

Salida

Un único entero: el costo total mínimo para construir los almacenes y transportar toda la producción.

Restricciones

• ~1 \leq N \leq 10^5~
• ~1 \leq x_i, p_i \leq 10^5~
• ~0 \leq c_i \leq 10^5~

Subtareas

Subtarea	Puntos	Restricciones
1	3	~N \leq 16~
2	18	~N \leq 5000~
3	31	~p_i = 1~, para todo ~i~
4	2	~c_i = 0~, para todo ~i~
5	46	Sin Restricciones Adicionales

Ejemplos de Entrada y Salida

Ejemplo #1 de Entrada

3
1 2 5
3 4 3
5 1 10

Ejemplo #1 de Salida

17

Explicación: Al construir almacenes en las fabricas ~2~ y ~3~ tenemos el costo: ~(3-1)*2+3+10=17~

Ejemplo #2 de Entrada

4
2 3 10
5 1 5
7 4 8
9 2 3

Ejemplo #2 de Salida

23