C. Сережа и две последовательности
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Сережи есть две последовательности a1, a2, ..., an и b1, b2, ..., bm, состоящие из целых чисел. Как-то раз Сереже было нечего делать, и он решил поиграть с последовательностями. Правила игры очень простые. Сережа делает несколько ходов, за один ход он может выполнить одно из следующих действий:

  1. Выбрать несколько (хотя бы один) первых элементов последовательности a (непустой префикс a), выбрать несколько (хотя бы один) первых элементов последовательности b (непустой префикс b); при этом элемент последовательности a с наибольшим индексом среди выбранных должен быть равен элементу последовательности b с наибольшим индексом среди выбранных; удалить выбранные элементы из последовательностей.
  2. Удалить все элементы обеих последовательностей.

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

Изначально у Сережи есть s единиц энергии и нет денег на электронном балансе. Какое максимальное количество денег Сережа может получить, играя с последовательностями, если в любой момент игры количество его энергии не должно становиться отрицательным?

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

Первая строка содержит целые числа n, m, s, e (1 ≤ n, m ≤ 105; 1 ≤ s ≤ 3·105; 103 ≤ e ≤ 104). Вторая строка содержит n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 105). Третья строка содержит m целых чисел b1, b2, ..., bm (1 ≤ bi ≤ 105).

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

Выведите единственное целое число — максимальную сумму в долларах, которую Сережа может получить.

Примеры
Входные данные
5 5 100000 1000
1 2 3 4 5
3 2 4 5 1
Выходные данные
3
Входные данные
3 4 3006 1000
1 2 3
1 2 4 3
Выходные данные
2