Bạn bị nhốt trong một tòa tháp tam giác vô hạn.

Tầng thứ \(k\) chứa đúng \(k\) phòng, được đánh số từ trái qua phải.

Mỗi phòng được xác định bởi cặp số \((w, e)\):

• \(w\): số tầng.
• \(e\): vị trí trong tầng (1 ≤ e ≤ w).

Từ mỗi phòng \((w, e)\), bạn có thể đi lên một trong hai phòng: \((w + 1, e)\) hoặc \((w + 1, e + 1)\).

Tuy nhiên, chỉ một hướng có sẵn:

• Nếu \(w + e\) là chẵn \(→\) đi được đến \((w + 1, e)\).
• Nếu \(w + e\) là lẻ \(→\) đi được đến \((w + 1, e + 1)\).

Tham khảo hình minh họa để dễ hiểu hơn:

Ví dụ như trong hình:

• Có đường đi từ \((1, 1)\) tới \((3, 2)\).
• Không thể đi từ \((2, 1)\) tới \((3, 1)\).

Bạn bắt đầu tại phòng \((1, 1)\). Tại mỗi bước, bạn được chọn:

• Di chuyển theo đường có sẵn tốn \(0\) điểm sức mạnh.

• Thay đổi đường đi của một phòng \((w, e)\):

  • Đảo hướng có sẵn sang hướng còn lại. Nếu đường hiện tại từ \((w, e)\) tới \((w + 1, e)\) có sẵn thì bạn có thể chuyển con đường này thành \((w, e)\) tới \((w + 1, e + 1)\) (và ngược lại).
  • Mỗi lần thay đổi tốn 1 điểm sức mạnh.

Cho danh sách \(n\) phòng cần ghé thăm, hãy tính tối thiểu tổng điểm sức mạnh cần thiết để đi từ phòng \((1, 1)\) và ghé qua tất cả \(n\) phòng, theo bất kỳ thứ tự nào.

Đầu vào

Dòng đầu tiên chứa số nguyên \(n\) \((1 \le n \le 2 * 10^5)\) - số phòng cần ghé qua.

\(n\) dòng tiếp theo, mỗi dòng chứa một cặp số \((w_i, e_i)\) biểu diễn phòng cần ghé thăm. \((1 \le i \le n, 1 \le e_i \le w_i \le 10^9)\)

Đầu ra

Một số nguyên duy nhất là tổng điểm sức mạnh tối thiểu cần để ghé thăm tất cả \(n\) phòng. Đầu vào đảm bảo luôn có đường đi giữa các điểm.

Giới hạn

\(10\%\) số test: \(n = 1\).

\(20\%\) số test: \(1 \le n \le 8, 1 \le e_i \le w_i \le 10^3\).

\(30\%\) số test: \(1 \le n \le 2000, 1 \le e_i \le w_i \le 10^6\).

\(40\%\) số test: Không có ràng buộc gì thêm.

Ví dụ