Tham quan du lịch đảo

Một khu du lịch có \(n\) hòn đảo, hòn đảo \(i\) có độ cao \(h_i\). Để di chuyển từ hòn đảo \(i\) đến hòn đảo \(j\), du khách có thể sử dụng tàu lượn với chi phí là max(\(0, h_j - h_i\)). Tuy nhiên, sau một thời
gian cho thuê tàu lượn, các nhà thầu đã áp giá sàn cho đảo thứ \(i\) là \(p_i\), cụ thể để di chuyển từ đảo \(i\) đến đảo \(j\), chi phí tính mới là: max(\(p_i, h_j - h_i\)).

Một du khách muốn đi thăm tất cả \(n\) hòn đảo bằng tàu lượn theo cách: bắt đầu từ hòn đảo \(1\), sử dụng tàu lượn để tới các hòn đảo khác, mỗi hòn đảo thăm đúng một lần rồi quay lại hòn đảo \(1\).

Yêu cầu: Hãy giúp du khách tìm hành trình di chuyển với tổng chi phí nhỏ nhất.

Input

• Dòng đầu chứa số nguyên dương \(n\ (n \le 10^5)\).
• Dòng thứ \(i\ (1 \le i \le n)\) trong \(n\) dòng sau chứa hai số nguyên không âm \(h_i, p_i\ (h_i, p_i \le 10^9)\).

Output

• Ghi ra một số là tổng chi phí nhỏ nhất tìm được.

Example

4
1 1
2 2
3 2
4 1

6

Scoring

• Subtask \(1\): \(n \le 20\).
• Subtask \(2\): Không có ràng buộc nào thêm.