Ограничения: время – 300ms/600ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Гвинт — любимая карточная игра Геральта, он готов играть в неё где угодно и когда угодно. Но даже любимые игры могут наскучить, поэтому ведьмак решил придумать для гвинта новые, улучшенные правила.
В гвинт со ставками играют `2` игрока, перед каждым из них лежит в открытую ряд из `N` карт c целочисленными (не обязательно уникальными) номиналами. Игроки в любой момент видят и все свои карты, и карты соперника. Сначала первый игрок объявляет величину ставки `S` (произвольное целое число от `1` до `N` включительно), сразу же отдаёт второму игроку `S` монет и выкладывает (в открытую) какие-нибудь `S` подряд идущих карт из своего ряда. Второй игрок должен в ответ также выложить `S` подряд идущих карт из своего ряда. Если второй выложил хотя бы `1` карту с номиналом, которого нет среди выложенных первым, то ставка считается побитой, и второй игрок получает от первого дополнительно `V` монет (то есть общий проигрыш первого равен `S + V`). Иначе, если номинал любой из выложенных карт второго игрока уже встречался среди выложенных карт первого, то ставка считается непобитой, и второй игрок выплачивает первому `V` монет (то есть общий выигрыш первого равен `V-S`). О величине `V` игроки договариваются заранее и менять её уже не могут.
Для заданных наборов карт и величины `V` определите максимальный выигрыш, который может получить первый игрок.
Первая строка входных данных содержит `2` положительных целых числа `N` (`1 <= N <= 10^5`) и `V` (`1 <= V <= 10^9`) — количество карт в наборах и награда за выигранную ставку соответственно.
Во второй строке содержится `N` положительных целых чисел `a_i` (`1 <= a_i <= 10^9`) — номиналы карт первого игрока в том порядке, в каком они лежат на столе.
В третьей строке содержится `N` положительных целых чисел `b_i` (`1 <= b_i <= 10^9`) — номиналы карт второго игрока в том порядке, в каком они лежат на столе.
Выведите единственное целое число — максимально возможный выигрыш первого игрока при оптимальной игре обоих. Выигрыш может быть нулевым или отрицательным (проигрыш).
```sample Пример ввода 1
4 10
3 3 2 5
5 3 5 5
```
```sample Пример вывода 1
7
```
Пояснение к примеру `1`: сделав ставку `3`, первый игрок выложит карты со второй по четвертую (номиналы `3`, `2` и `5`). Какие бы карты ни выложил второй, он не сможет побить такую ставку, так как имеет только карты `3` и `5`. Общий выигрыш первого в этом случае равен `10-3 = 7`. Сделав ставку величиной `1` или `2`, первый игрок потеряет `11` или `12` монет соответственно, так как любую из таких ставок второй игрок сможет побить.
```sample Пример ввода 2
5 1
1 2 2 2 3
1 2 3 1 1
```
```sample Пример вывода 2
-2
```
Пояснение к примеру `2`: единственный способ сделать ставку, которую второй не сможет побить — это выложить сразу все свои карты. В этом случае первый игрок заплатит `5` и выиграет `1`, то есть суммарный результат равен `-4`. Поэтому выгоднее будет сделать минимально возможную ставку в 1 карту и минимизировать свои затраты.
```sample Пример ввода 3
2 10
1 1
2 2
```
```sample Пример вывода 3
-11
```
Пояснение к примеру `3`: ставка в любом случае будет побита, поэтому для минимизации затрат первый вновь должен поставить 1 любую карту.
Начало
Рабочее место участника
Сканирование, метод двух указателей