Hội trường

Bạn đang quản lý một hội trường. Có \(n\) lượt đăng kí sử dụng hội trường, lượt thứ \(i\) là khoảng thời gian \([l_i, r_i]\), nghĩa là đăng kí sử dụng hội trường từ thời điểm \(l_i\) đến \(r_i\) (tính cả hai đầu). Tổng thời gian sử dụng của lượt này là \(r_i - l_i + 1\).

Tại một thời điểm, hội trường chỉ có thể tiếp nhận nhiều nhất một lượt đăng kí. Hai lượt được gọi là giao nhau nếu chúng có ít nhất một thời điểm trùng nhau. Ví dụ, hai lượt \([3, 5]\) và \([5, 7]\) được xem là giao nhau vì cùng chứa thời điểm \(5\).

Nhiệm vụ của bạn là chọn ra một số lượt đăng kí sao cho không có hai lượt nào giao nhau, và tổng thời gian sử dụng hội trường là lớn nhất.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 10^5\)) --- số lượt đăng kí.

• \(n\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(l_i, r_i\) (\(1 \le l_i \le r_i \le 10^5\)) --- khoảng thời gian của lượt đăng kí thứ \(i\).

Output

In ra một số nguyên duy nhất --- tổng thời gian sử dụng hội trường lớn nhất có thể đạt được mà không có hai lượt giao nhau.

Scoring

• Có \(50\%\) số điểm ứng với \(1 \le n \le 1000\).

• \(50\%\) số điểm còn lại không có ràng buộc thêm.

Notes

Chọn hai lượt đăng kí \([2, 5]\) và \([6, 8]\) để đạt tổng thời gian là \(4 + 3 = 7\).