Como científico malvado, has descubierto cómo crear gelatinas más grandes y aterradoras en tu laboratorio secreto. Dispuestas alrededor de tu mesa de laboratorio circular hay un arreglo cíclico de $N$ gelatinas rectangulares, cada una con una altura y anchura determinadas. Ten en cuenta que la primera y la última gelatina son adyacentes.

Puedes fusionar dos gelatinas parentales adyacentes para producir una gelatina combinada con una altura igual al máximo de las alturas de las dos gelatinas parentales y una anchura igual al máximo de las anchuras de las dos gelatinas parentales. La gelatina fusionada reemplaza a las parentales en su lugar dentro del arreglo cíclico (que ahora es un elemento más corto) y, en principio, podría fusionarse de nuevo con uno de sus dos vecinos.

Deseas maximizar la suma de las áreas de tus gelatinas realizando esta operación de fusión cualquier número de veces. Después de todo, ¡cuanta más área total puedan cubrir tus gelatinas, más ciudades podrás conquistar!

Entrada

La primera línea de la entrada contiene un entero $N$ ($1 \le N \le 3 \cdot 10^5$), el número de gelatinas inicialmente en tu mesa de laboratorio.

Las siguientes $N$ líneas describen estas gelatinas, en orden. La $i$-ésima línea contiene dos enteros separados por espacios $h_i$ y $w_i$ ($1 \le h_i, w_i \le 10^6$), la altura y la anchura de la $i$-ésima gelatina.

Salida

Imprime un solo entero: la suma de las áreas de las gelatinas que permanecen en tu arreglo cíclico después de realizar cualquier número de operaciones de fusión para maximizar óptimamente esta suma.

Ejemplos

Entrada 1

2
6 3
2 7

Salida 1

42

Entrada 2

4
1 5
10 10
5 1
6 7

Salida 2

152

Entrada 3

5
6 2
5 1
1 5
2 7
1 2

Salida 3

67

Entrada 4

1
380385 222650

Salida 4

84692720250