Gom Lô Đất · canuc80k4206

Có $n$ lô đất hình chữ nhật; lô $i$ có chiều rộng $w_{i}$ và chiều cao $h_{i}$ . Một giao dịch có thể mua bất kỳ nhóm lô nào, với chi phí bằng tích giữa chiều rộng lớn nhất và chiều cao lớn nhất trong nhóm.

Bạn được chia các lô thành nhiều giao dịch. Hãy tìm tổng chi phí nhỏ nhất để mua hết; một lô bị chứa hoàn toàn trong lô khác có thể đi cùng mà không làm tăng kích thước giao dịch.

Input

Dòng đầu chứa $n$ .
$n$ dòng tiếp theo, mỗi dòng chứa $w_{i}, h_{i}$ .

Output

In tổng chi phí nhỏ nhất.

Constraints

$1 \leq n \leq 5 \cdot 1 0^{4}$ .
$1 \leq w_{i}, h_{i} \leq 1 0^{6}$ .

Scoring

Subtask $1$ ( $50%$ số điểm): kích thước chính không vượt quá $60$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Mua lô $(2, 5)$ riêng tốn $10$ , rồi mua hai lô còn lại chung trong khung $6 \times 3$ tốn $18$ . Tổng tối ưu là $28$ .