땅따먹기

농부 상헌이는 선재의 부동산에서 땅 $N$개를 모두 사려고 한다. 각 땅은 가로 $W_i$, 세로 $H_i$인 직사각형이다.

원래 땅 하나의 가격은 $W_i \times H_i$이지만, 요즘 장사가 잘 안 되는 선재는 다음과 같은 묶음 할인을 진행한다.

• 여러 땅을 하나의 묶음으로 사면, 그 묶음의 가격은 (묶음에 속한 땅들의 $W_i$ 중 최댓값) $\times$ (묶음에 속한 땅들의 $H_i$ 중 최댓값)이다.

상헌이는 $N$개의 땅을 여러 묶음으로 나누어 모두 사려고 하며, 각 땅은 정확히 하나의 묶음에 속해야 한다. 땅을 어떻게 묶느냐에 따라 총 가격이 달라질 때, 모든 땅을 사기 위한 최소 비용을 구하여라.

첫째 줄에 땅의 개수 $N$이 주어진다. ($1 \le N \le 50000$)

이어지는 $N$개의 줄에 각 땅의 가로 $W_i$와 세로 $H_i$가 공백으로 구분되어 주어진다. ($1 \le W_i, H_i \le 1000000$)

모든 땅을 사기 위한 최소 비용을 한 줄에 출력한다.

예를 들어 땅이 $(100, 1)$, $(15, 15)$, $(20, 5)$, $(1, 100)$ 네 개라면, $\{(100,1)\}$, $\{(1,100)\}$, $\{(15,15),(20,5)\}$의 세 묶음으로 나누어 살 수 있다. 이때 비용은 $100 \times 1 + 1 \times 100 + 20 \times 15 = 500$이다.