У Сережи есть две последовательности a1, a2, ..., an и b1, b2, ..., bm, состоящие из целых чисел. Как-то раз Сереже было нечего делать, и он решил поиграть с последовательностями. Правила игры очень простые. Сережа делает несколько ходов, за один ход он может выполнить одно из следующих действий:
- Выбрать несколько (хотя бы один) первых элементов последовательности a (непустой префикс a), выбрать несколько (хотя бы один) первых элементов последовательности b (непустой префикс b); при этом элемент последовательности a с наибольшим индексом среди выбранных должен быть равен элементу последовательности b с наибольшим индексом среди выбранных; удалить выбранные элементы из последовательностей.
- Удалить все элементы обеих последовательностей.
Первое действие стоит e единиц энергии и приносит на электронный баланс Сергея один доллар. Второе действие стоит столько единиц энергии, сколько элементов удалил Сережа из последовательностей до выполнения этого действия. Выполнив второе действие Сережа получает все деньги, накопившиеся на его электронном балансе за время игры.
Изначально у Сережи есть s единиц энергии и нет денег на электронном балансе. Какое максимальное количество денег Сережа может получить, играя с последовательностями, если в любой момент игры количество его энергии не должно становиться отрицательным?