Là một nhà khoa học độc ác, bạn đã tìm ra cách tạo ra những con thạch to hơn và đáng sợ hơn trong phòng thí nghiệm bí mật của mình. Được sắp xếp xung quanh bàn thí nghiệm hình tròn của bạn là một mảng vòng gồm $N$ con thạch hình chữ nhật, mỗi con có một chiều cao và chiều rộng nhất định. Lưu ý rằng con thạch đầu tiên và con thạch cuối cùng nằm kề nhau.

Minh họa về sự hợp nhất thạch.

Bạn có thể hợp nhất hai con thạch kề nhau để tạo ra một con thạch kết hợp có chiều cao bằng giá trị lớn nhất trong hai chiều cao của thạch cha và chiều rộng bằng giá trị lớn nhất trong hai chiều rộng của thạch cha. Con thạch sau khi hợp nhất sẽ thay thế vị trí của hai con thạch cha trong mảng vòng (lúc này mảng sẽ ngắn đi một phần tử) và về nguyên tắc có thể tiếp tục được hợp nhất với một trong hai con thạch láng giềng của nó.

Bạn muốn tối đa hóa tổng diện tích của các con thạch bằng cách thực hiện thao tác hợp nhất này bất kỳ số lần nào. Suy cho cùng, tổng diện tích các con thạch càng lớn, bạn càng có thể chinh phục được nhiều thành phố hơn!

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên $N$ ($1 \le N \le 3 \cdot 10^5$), số lượng thạch ban đầu trên bàn thí nghiệm của bạn.

$N$ dòng tiếp theo mô tả các con thạch này theo thứ tự. Dòng thứ $i$ chứa hai số nguyên cách nhau bởi dấu cách $h_i$ và $w_i$ ($1 \le h_i, w_i \le 10^6$), lần lượt là chiều cao và chiều rộng của con thạch thứ $i$.

Dữ liệu ra

In ra một số nguyên duy nhất: tổng diện tích của các con thạch còn lại trong mảng vòng sau khi bạn thực hiện bất kỳ số lần thao tác hợp nhất nào để tối đa hóa tổng diện tích này một cách tối ưu.

Ví dụ

Ví dụ 1

2
6 3
2 7

Ví dụ 1

42

Ví dụ 2

4
1 5
10 10
5 1
6 7

Ví dụ 2

152

Ví dụ 3

5
6 2
5 1
1 5
2 7
1 2

Ví dụ 3

67

Ví dụ 4

1
380385 222650

Ví dụ 4

84692720250