Statement is not available in English language
C. Крош и удаления
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Кроша есть массив из $$$n$$$ элементов, пронумерованных слева направо от $$$1$$$ до $$$n$$$. Каждый элемент имеет значение $$$a_i$$$ и стоимость удаления $$$c_i$$$. Крош играет на этом массиве в следующую игру. За один ход он берет пару соседних элементов и удаляет из них наименьший по значению, при этом платит стоимость удаления наименьшего по значению элемента за эту операцию. То есть, удаляем наименьший элемент и платим его стоимость удаления. У Кроша есть сумма $$$s$$$, которую можно потратить на удаление элементов. Помогите ему найти наибольшее значение, которое может принять минимум этого массива после нуля или более операций. Обратите внимание, в массиве должен остаться хотя бы один элемент, так как для него не существует пары. При удалении элементы смещаются, то есть не остаётся пропусков.

Входные данные

В первой строке вам даны два числа $$$1 \le n \le 10^5$$$ и $$$0 \le s \le 10^{18}$$$. В следующей строке заданы значения элементов $$$0 \le a_i \le 10^9$$$. В следующей строке даны стоимости удаления $$$0 \le c_i \le 10^9$$$.

Система оценки
  • Подзадача 1 (50 баллов) $$$n \le 100$$$
  • Подзадача 2 (50 баллов) без дополнительных ограничений, необходимые подазадачи – 1
Выходные данные

Выведите одно число - наибольшее значение, которое может принять минимум в массиве.

Пример
Входные данные
6 12
3 1 4 2 5 6
3 2 5 5 2 7
Выходные данные
4