Haybale Feast

Interview

Time limit2sMemory limit512 MB

Summary

Pick a contiguous block whose flavor sums to at least M while minimizing the block's maximum spiciness.

Level: Medium6 of 10
Topics: Two pointers, Sliding window, Binary search, Prefix sum
Solved: No attempts yet

Problem

Farmer John is preparing a meal for his cows. His barn holds $N$ haybales ( $1 \le N \le 100{,}000$ ). The $i$ th haybale has flavor $F_i$ ( $1 \le F_i \le 10^9$ ) and spiciness $S_i$ ( $1 \le S_i \le 10^9$ ).

The meal is a single course, which is a contiguous interval of one or more haybales. Farmer John cannot change the order of the haybales. The total flavor of the meal is the sum of the flavors in the interval, and the spiciness of the meal is the maximum spiciness among the haybales in the interval.

Find the minimum spiciness a single-course meal can have, given that its total flavor must be at least $M$ ( $1 \le M \le 10^{18}$ ).

Input

The first line contains the integers $N$ and $M$ , the number of haybales and the minimum total flavor the meal must have. Each of the next $N$ lines describes one haybale with two integers, the flavor $F$ and then the spiciness $S$ .

Output

Print, on a single line, the minimum spiciness of a single-course meal that meets the minimum flavor requirement. At least one such meal always exists.

Examples3

Example 1
Input
```
5 10
4 10
6 15
3 5
4 9
3 6
```
Expected output
```
9
```
Example 2
Input
```
1 1
1 1
```
Expected output
```
1
```
Example 3
Input
```
8 1
5 8
1 3
9 7
2 1
4 6
7 2
3 9
6 5
```
Expected output
```
1
```