Bác nông dân John đang chuẩn bị một bữa ăn ngon cho đàn bò! Trong chuồng, bác có \(N\) kiện cỏ khô (\(1 \leq N \leq 100{,}000\)). Kiện cỏ thứ \(i\) có độ ngon \(F_i\) (\(1 \leq F_i \leq 10^9\)) và độ cay \(S_i\) (\(1 \leq S_i \leq 10^9\)).

Bữa ăn chỉ gồm một món, được tạo bởi một đoạn liên tiếp chứa một hoặc nhiều kiện cỏ khô liên tiếp (bác nông dân John không thể thay đổi thứ tự các kiện cỏ). Tổng độ ngon của bữa ăn là tổng độ ngon của các kiện cỏ trong đoạn. Độ cay của bữa ăn là độ cay lớn nhất trong số tất cả các kiện cỏ thuộc đoạn.

Bác nông dân John muốn xác định độ cay nhỏ nhất mà bữa ăn một món có thể đạt được, với điều kiện tổng độ ngon phải ít nhất là \(M\) (\(1 \leq M \leq 10^{18}\)).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), lần lượt là số kiện cỏ khô và tổng độ ngon tối thiểu mà bữa ăn phải có. \(N\) dòng tiếp theo mô tả \(N\) kiện cỏ, mỗi dòng chứa hai số nguyên: trước tiên là độ ngon \(F\), sau đó là độ cay \(S\).

Dữ liệu ra

In ra độ cay nhỏ nhất của một bữa ăn một món thỏa mãn yêu cầu về độ ngon tối thiểu. Luôn tồn tại ít nhất một bữa ăn một món thỏa mãn yêu cầu về độ ngon.

Ví dụ

5 10
4 10
6 15
3 5
4 9
3 6

9

Nguồn

USACO 2017 December Contest, Gold — Haybale Feast

Tác giả bài toán: Christopher Chang và Allen Chen.