Hưng là một người thích những cơn mưa, nhưng mỗi khi ngắm mưa lại gợi cho cậu những kỷ niệm buồn. Để vơi đi nỗi buồn, Hưng đã mang các khối hình hộp chữ nhật ra chơi.

Hưng có $N$ khối hình hộp chữ nhật có chiều rộng bằng nhau. Hưng sẽ sắp xếp lại những khối chữ nhật đó để thu thập lượng mưa lớn nhất. Để đạt được điều này, cậu sẽ đặt $N$ khối trên một hàng, không được phép có khoảng trống giữa các khối. Cậu có thể xoay một số khối chữ nhật để đổi chiều dài và chiều cao hoặc giữ nguyên nhưng không được thay đổi chiều rộng.

Cách sắp xếp các khối hình chữ nhật sẽ tạo ra các "bể nước" và Hưng sẽ thu được nước mưa bằng đúng diện tích các bể. Vì đang còn những u sầu nên Hưng không thể nghĩ ra cách xếp tối ưu. Bạn hãy giúp cậu tìm cách sắp xếp các khối hình hộp chữ nhật sao cho lượng nước mưa thu được là nhiều nhất.

Input

Dòng đầu tiên là số nguyên dương $N$ $(3\le N\le 3\cdot {10}^5)$ — số lượng khối hình hộp chữ nhật mà Hưng có.

$N$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $w_i$, $h_i$ $(1\le w_i,h_i\le {10}^6)$ — chiều dài và chiều cao của hình chữ nhật thứ $i$.

Output

In ra một số nguyên dương duy nhất, biểu thị diện tích nước tối đa mà Hưng có thể thu được nếu anh ta sắp xếp các khối hình hộp chữ nhật một cách tối ưu.

Scoring

Sample Input 1

3
4 3
2 6
5 1

Sample Output 1

15

Sample Input 2

3
1 2
2 1
1 1

Sample Output 2

1

Notes

Ở ví dụ 1: Đặt các hình chữ nhật kề nhau theo cặp (chiều dài, chiều cao) như sau: (3, 4) (5, 1) (2, 6).

Ở ví dụ 2: Đặt các hình chữ nhật kề nhau theo cặp (chiều dài, chiều cao) như sau: (1, 2) (1, 1) (1, 2).