Свято сіна
Фермер Джон готує делікатесну їжу для своїх корів. У його коморі є n стогів сіна. i-ий стіг має певний смак f[i] (1 ≤ f[i] ≤ 10^9) і певну пряність s[i] (1 ≤ s[i] ≤ 10^9).
Їжа буде складатися з неперервного інтервалу, що містить один або більше послідовних стогів сіна (їх порядок змінювати не можна). Загальний смак їжі дорівнює сумі смаків на інтервалі. Загальна пряність їжі - це максимум з пряностей на інтервалі.
Фермер Джон хоче визначити мінімальну пряність, яку можна досягти, щоб загальний смак був не менше m.
Вхідні дані
Перший рядок містить цілі числа n (1 ≤ n ≤ 10^5) і m (1 ≤ m ≤ 10^18) - кількість стогів сіна і мінімальний смак, якого потрібно досягти, відповідно. Наступні n рядків описують n стогів сіна парою чисел у рядку - перше число це смак f, а друге - пряність s.
Вихідні дані
Виведіть мінімальну пряність, яку можна досягти при виконанні вимоги про мінімальний смак. Гарантується існування розв'язку.