Информатика мұғалімі Ернаттың ұзындығы \(n\) болатын массиві бар, элементтері \(1\)-ден \(n\)-ге дейін нөмірленген. \(i\)-ші элементтің мәні \(a_i\), ал оны жою құны \(c_i\) деп берілген.

Ернат келесі ойынды ойнайды. Бір қадамда ол көршілес екі элементтен тұратын жұпты таңдайды да, мәні кіші элементті өшіреді (егер мәндері тең болса — кез келгенін). Бұл кезде ол өшірілген элемент үшін оның жою құнын, яғни сәйкес \(c_i\) мәнін төлейді. Элемент өшкен соң массивтегі элементтер жылжиды, яғни бос орын қалмайды.

Ернаттың жоюларға жұмсай алатын жалпы сомасы \(s\). Ол бірнеше (мүмкін, нөл) қадам жасап, қалған массивтің минимал элементі мүмкіндігінше үлкен болғанын қалайды. Массивте кем дегенде бір элемент қалуы тиіс.

Енгізу

Бірінші жолда екі бүтін сан \(n\) және \(s\) берілген (\(1 \le n \le 10^5\), \(0 \le s \le 10^{18}\)). Екінші жолда \(n\) бүтін сан \(a_i\) берілген (\(0 \le a_i \le 10^9\)). Үшінші жолда \(n\) бүтін сан \(c_i\) берілген (\(0 \le c_i \le 10^9\)).

Шығару

Бір бүтін санды шығарыңыз — жоюлардың жиынтық құны \(s\)-тен аспайтын қадамдардан кейін массивтің минимумының алуы мүмкін ең үлкен мәні.

Бағалау жүйесі

Мысалдар

Енгізу 1

4 5
3 1 7 2
4 2 5 3

Жауап 1

3

Ескертпелер

Алдымен мәні \(1\) элементті өшіруге болады (құны \(2\)), содан кейін мәні \(2\) элементті өшіреміз (құны \(3\)). Жалпы шығын \(5\) болады, нәтижесінде \([3, 7]\) массиві қалады, оның минимумы \(3\)-ке тең. \(s = 5\) бюджетімен минимумды \(3\)-тен үлкен ету мүмкін емес.