Minimum Spiciness Haybale Meal

Farmer John is preparing a delicious meal for his cows using N haybales. The ith haybale has a flavor \(F_i\) and a spiciness \(S_i\). The meal consists of a contiguous interval (one or more consecutive haybales). The total flavor of the meal is the sum of the flavors in the interval, and its spiciness is defined as the maximum spiciness among the haybales in the interval.

Farmer John wants the meal to have a total flavor of at least \(M\), while minimizing the spiciness. In other words, find a contiguous subarray such that the sum of the flavors \(\ge M\), and among all such intervals, the maximum spiciness is minimized.

Constraints:

• \(1 \le N \le 100{,}000\)
• \(1 \le F_i \le 10^9\)
• \(1 \le S_i \le 10^9\)
• \(1 \le M \le 10^{18}\)

inputFormat

The first line contains two integers \(N\) and \(M\), representing the number of haybales and the minimum total flavor required.

The next \(N\) lines each contain two integers \(F_i\) and \(S_i\) representing the flavor and spiciness of the \(i\)th haybale, respectively.

outputFormat

Output a single integer representing the minimum possible spiciness of a contiguous interval of haybales that has a total flavor of at least \(M\).

sample

3 5
2 3
3 5
2 2

5