Haybale Feast#10517
Farmer John is preparing a delicious meal for his cows! In his barn, he has haybales. The -th haybale has a certain flavor f_i~(1 \le f_i \le 10^9) and a certain spiciness s_i~(1 \le s_i \le 10^9).
The meal will consist of a single course, which must be a contiguous interval containing one or more consecutive haybales (Farmer John cannot change the order of the haybales). The total flavor of the meal is the sum of the flavors of the haybales in the interval. The spiciness of the meal is the maximum spiciness among all haybales in the interval.
Farmer John would like to determine the minimum possible spiciness of his single-course meal, given that its total flavor must be at least .
The first line contains two integers n~(1 \le n \le 10^5) and m~(1 \le m \le 10^{18}), representing the number of haybales and the minimum total flavor required for the meal, respectively. The next lines each describe one of the haybales with two integers: first the flavor and then the spiciness .
Print the minimum spiciness of a single-course meal whose total flavor is at least . It is guaranteed that at least one single-course meal satisfies the flavor requirement.
Example 1