En tant que scientifique maléfique, vous avez découvert comment créer des gelées plus grosses et plus effrayantes dans votre laboratoire secret. Disposées autour de votre paillasse circulaire, se trouvent $N$ gelées rectangulaires dans un tableau cyclique, chacune ayant une hauteur et une largeur données. Notez que la première et la dernière gelée sont adjacentes.

Illustration de la fusion de gelées.

Vous pouvez fusionner deux gelées parentes adjacentes pour produire une gelée combinée dont la hauteur est égale au maximum des hauteurs des deux gelées parentes et dont la largeur est égale au maximum des largeurs des deux gelées parentes. La gelée fusionnée remplace les parents à leur emplacement dans le tableau cyclique (qui contient désormais un élément de moins) et pourrait, en principe, être fusionnée à nouveau avec l'un de ses deux voisins.

Vous souhaitez maximiser la somme des aires de vos gelées en effectuant cette opération de fusion un nombre quelconque de fois. Après tout, plus vos gelées peuvent couvrir une surface totale importante, plus vous pouvez conquérir de villes !

Entrée

La première ligne de l'entrée contient un entier $N$ ($1 \le N \le 3 \cdot 10^5$), le nombre de gelées initialement sur votre paillasse.

Les $N$ lignes suivantes décrivent ces gelées, dans l'ordre. La $i$-ième ligne contient deux entiers séparés par un espace $h_i$ et $w_i$ ($1 \le h_i, w_i \le 10^6$), la hauteur et la largeur de la $i$-ième gelée.

Sortie

Affichez un seul entier : la somme des aires des gelées qui restent dans votre tableau cyclique après avoir effectué un nombre quelconque d'opérations de fusion pour maximiser cette somme de manière optimale.

Exemples

Entrée 1

2
6 3
2 7

Sortie 1

42

Entrée 2

4
1 5
10 10
5 1
6 7

Sortie 2

152

Entrée 3

5
6 2
5 1
1 5
2 7
1 2

Sortie 3

67

Entrée 4

1
380385 222650

Sortie 4

84692720250