Farmer John đang chuẩn bị một bữa ăn ngon cho những con bò của mình! Trong kho của ông ấy, có \(N\) bó rơm. Bó rơm thứ \(i\) có một hương vị \(a_i\) và độ cay \(b_i\).

Bữa ăn sẽ bao gồm một khoảng liên tiếp chứa một hoặc nhiều bó rơm liên tiếp (Farmer John không thể thay đổi thứ tự của các bó rơm). Tổng hương vị của bữa ăn là tổng của các hương vị trong khoảng đó. Độ cay của bữa ăn là độ cay cao nhất của tất cả các bó rơm trong khoảng đó.

Yêu cầu: Xác định độ cay tối thiểu mà bữa ăn có thể đạt được, với điều kiện tổng hương vị phải ít nhất là \(M\).

Input

• Dòng đầu tiên chứa hai số nguyên \(N,M(1 ≤ N ≤ 10^5, 1 ≤ M ≤ 10^{18})\) - số lượng bó rơm và tổng hương vị tối thiểu mà bữa ăn phải có, tương ứng.

• \(N\) dòng tiếp, dòng thứ \(i\) trong \(N\) dòng chứa hai số nguyên \(a_i , b_i (a_i ≤ 10^9, b_i≤ 10^9)\) tương ứng là hương vị và độ cay của bó cỏ thứ \(i\).

Output

• In ra độ cay tối thiểu mà bữa ăn có thể đạt được, với điều kiện tổng hương vị phải ít nhất là \(M\). Luôn có ít nhất một bữa ăn thỏa mãn yêu cầu đề bài.

Sample Input

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

Sample Output

9