Алгоритмы поиска

Правила новой телевизионной викторины следующие. В ряд расположены \(n\) ячеек, пронумерованных от \(1\) до \(n\), в \(i\)-й ячейке находится \(a_i\) монет.

Игрок может выбрать целое число \(b\) и заплатить \(b\) монет. Тогда ведущий забирает монеты из всех ячеек, где лежит не более \(b\) монет, соответствующие ячейки становятся пустыми. После этого среди любых \(k\) подряд идущих ячеек должно быть не менее \(m\) пустых. После этого игрок забирает все оставшиеся на поле монеты, если он забрал \(a\) монет, его выигрыш составит \(a-b\) монет.

Помогите игроку понять, какое максимальный выигрыш он может гарантировать.

Формат входных данных
На первой строке ввода находятся целые числа \(n\), \(k\) и \(m\) (\(1 \le m < k \le n \le 200\,000\)).

На второй строке находятся \(n\) целых чисел \(a_i\) (\(1 \le a_i \le 10^9\)).

Формат выходных данных
Выведите одно число: какой максимальной выигрыш может гарантировать себе игрок.

Примечание
В первом примере игрок выбирет \(b = 5\). После удаления монет из ячеек, в которых лежит не более чем по \(5\) монет, количество монет в ячейках оказывается равно \([0, 7, 0, 0, 0, 9, 0, 6]\), суммарно он забирает из ячеек \(22\) монеты, с учетом ранее отданных \(5\) монет выигрыш игрока составляет \(17\) монет.

Во втором примере, чтобы добиться, чтобы среди любых двух подряд идущих ячеек была хотя бы одна пустая, игроку приходится выбрать \(b = 2\). После этого монет в ячейках нет, и выигрыш игрока оказывается отрицательным: \(-2\).

Влад наконец-то достиг позиции тимлида в команде, но теперь у него совсем нет времени на дорогу домой, и ему придется спать в офисе. К сожалению, не все IT-компании могут позволить себе просторный и удобный коворкинг, в котором можно подремать, поэтому Влад будет спать на офисных стульях.

В офисе есть \(n\) стульев, \(i\)-й из которых имеет высоту \(h_i\) и ширину \(w_i\). Влад планирует выбрать любой набор офисных стульев \([i_1, i_2, \ldots, i_k]\) и расположить в ряд, чтобы на них можно было лечь. Рост Влада равен \(H\), поэтому, чтобы он мог удобно лежать, необходимо, чтобы суммарная ширина выбранных стульев была не меньше \(H\), то есть \[\sum\limits_{j=1}^k w_{i_j} \ge H \text{.}\]

Очевидно, что спать на стульях разной высоты неудобно. Назовем неудобностью выбранного набора максимальную разность высот двух соседних стульев в ряду, то есть \(\max\limits_{j=2}^k |h_{i_j} - h_{i_{j-1}}|\). Если набор состоит из одного стула, его неудобность равна \(0\).

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

Формат входных данных
В первой строке ввода через пробел даны два целых числа \(n\) и \(H\) — количество стульев и рост Влада (\(1 \le n \le 2 \cdot 10^5\); \(1 \le H \le 10^9\)).

Во второй строке ввода через пробел перечислены \(n\) целых чисел \(h_i\) — высоты стульев (\(1 \le h_i \le 10^9\)). В третьей строке в том же формате перечислены \(n\) целых чисел \(w_i\), равных ширине стульев (\(1 \le w_i \le 10^9\)).

Гарантируется, что \(H\) не превосходит суммы всех \(w_i\).

Формат выходных данных
Выведите единственное число — минимальное возможное неудобство среди всех подходящих наборов.

Замечание

В первом примере нужно выставить стулья \(2\) и \(4\) в любом порядке.

Во втором примере можно выбрать, например, следующие наборы: \([1, 5]\), \([2, 4, 3]\). Обратите внимание, что порядок стульев в наборе важен: неудобность набора \([2, 3, 4]\) равна \(\max(|5 - 3|, |4 - 5|) = \max(2, 1) = 2\), что больше, чем для набора \([2, 4, 3]\).

Два сотрудника одной известной компании Алиса и Боб предложили тимлиду два решения возникшего в критическом месте бага. Теперь Алиса подозревает, что сотрудник Боб просто взял ее код и добавил в него не влияющие на функциональность символы, чтобы создать впечатление более интенсивной работы.

Компания пишет на эзотерическом языке программирования, похожем на Malbolge, поэтому код каждого из сотрудников представляет из себя строчку из маленьких латинских букв. Код Алисы — строка \(t\), а код Боба — строка \(s\).

Поскольку клавиатура Боба сломана, он может печатать ровно два символа за раз, то есть может вставлять в любое место строки два любых (не обязательно одинаковых) символа. После заявления Алисы о подозрении Боба в плагиате их начальник начал анализировать строки \(s\) и \(t\), пытаясь понять, мог ли Боб получить строку \(s\) из строки \(t\) со своей сломанной клавиатурой. Для этого он пытается постепенно удалять из строки \(s\) по два соседних символа, пока не получит в итоге строrку \(t\).

Помогите выяснить, виноват ли Боб в плагиате: определите, можно ли получить строку \(t\) из строки \(s\), вырезая из нее произвольное количество раз по два стоящих рядом символа.

Входные данные
В первой строке дана строка \(s\), состоящая из маленьких латинских букв от ‘a’ до ‘z’ (\(1 \le |s| \le 2 \cdot 10^5\)).

Во второй строке дана строка \(t\), также состоящая из маленьких латинских букв (\(1 \le |t| \le |s|\)).

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

В качестве ответа выведите <<YES>>, если из \(s\) можно получить \(t\) удалениями двух символов подряд, и <<NO>> в противном случае.

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.