Farmer John vừa nhận một lô gồm \(N\) kiện cỏ khô lớn (\(1 \le N \le 4000\)) và đặt chúng tại nhiều vị trí khác nhau dọc theo con đường dẫn đến chuồng. Không may, ông hoàn toàn quên mất rằng cô bò Bessie đang gặm cỏ dọc con đường, và giờ cô có thể đã bị mắc kẹt giữa các kiện cỏ!

Mỗi kiện cỏ \(j\) có kích thước \(S_j\) và một vị trí phân biệt \(P_j\) cho biết nơi nó nằm trên con đường một chiều. Bessie bắt đầu tại một vị trí không có kiện cỏ nào và có thể tự do di chuyển dọc theo đường, kể cả đi tới đúng vị trí của một kiện cỏ, nhưng cô không thể đi xuyên qua vị trí này. Tuy nhiên, nếu chạy theo cùng một hướng trên quãng đường dài \(D\), cô sẽ đạt đủ tốc độ để phá xuyên qua và loại bỏ vĩnh viễn bất kỳ kiện cỏ nào có kích thước nhỏ hơn nghiêm ngặt \(D\). Dĩ nhiên, sau khi làm vậy, cô có thể có thêm không gian để lấy đà lao vào các kiện cỏ khác và tiếp tục phá chúng.

Bessie có thể thoát ra ngoài nếu cuối cùng cô phá xuyên qua được kiện cỏ ngoài cùng bên trái hoặc ngoài cùng bên phải. Hãy tính tổng độ dài của phần đường gồm các vị trí bắt đầu có giá trị thực mà từ đó Bessie không thể thoát. Chẳng hạn, nếu Bessie không thể thoát khi bắt đầu giữa hai kiện cỏ ở vị trí 1 và 5, thì chúng tạo nên một phần đường có độ dài 4 mà từ đó cô không thể thoát.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N\) dòng tiếp theo mô tả một kiện cỏ, gồm hai số nguyên cho biết kích thước và vị trí của kiện cỏ; mỗi số đều nằm trong khoảng \(1 \ldots 10^9\).

Dữ liệu ra

In một số nguyên duy nhất: độ dài của phần đường mà từ đó Bessie không thể thoát.

Ví dụ

5
8 1
1 4
8 8
7 15
4 20

14

Nguồn

USACO 2015 US Open, Bronze — Trapped in the Haybales (Bronze). Tác giả đề: Brian Dean, 2015.

https://usaco.org/index.php?page=viewproblem2&cpid=547