Farmer John vừa nhận một lô gồm \(N\) kiện cỏ khô lớn (\(1 \le N \le 100{,}000\)) và đặt chúng tại nhiều vị trí khác nhau dọc theo con đường nối chuồng với nhà của ông. 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. Cô bò Bessie hiện đang ở vị trí \(B\), nơi không có kiện cỏ nào.

Bessie 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.

FJ hiện đang sơn lại nhà và chuồng, nên ông muốn chắc chắn rằng Bessie không thể đến được nơi nào trong hai nơi đó (bò và sơn còn ướt không phải là một sự kết hợp tốt!). Vì vậy, FJ muốn đảm bảo Bessie không bao giờ phá xuyên qua kiện cỏ ngoài cùng bên trái hoặc ngoài cùng bên phải, để cô vẫn bị giữ lại giữa các kiện cỏ. FJ có thể thêm cỏ vào đúng một kiện cỏ do ông chọn để giúp giữ Bessie mắc kẹt. Hãy giúp ông xác định lượng cỏ ít nhất cần thêm vào một kiện cỏ nào đó để đảm bảo Bessie vẫn bị mắc kẹt.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và vị trí ban đầu \(B\) của Bessie. 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 kích thước và vị trí đều nằm trong khoảng \(1 \ldots 10^9\).

Dữ liệu ra

In một số nguyên duy nhất: lượng cỏ ít nhất FJ cần thêm để ngăn Bessie thoát ra. In -1 nếu không thể ngăn Bessie thoát.

Ví dụ

5 7
8 1
1 4
3 8
12 15
20 20

4

Nguồn

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

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