5. Интересная эстафета
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Есть две команды, в каждой по $$$n$$$ лыжников. Первая команда стартует из пункта A, вторая – из пункта B (назовём их командой A и командой B соответственно), находящихся на одной прямой на расстоянии $$$d$$$ друг от друга. Участники эстафеты двигаются навстречу друг другу в противоположный пункт. Пусть лыжники пронумерованы от 1 до $$$2n$$$, причём лыжники с нечетными номерами стартуют из пункта A, а лыжники с чётными номерами – из пункта B. Так как это очень подготовленные участники, будем считать, что все они движутся с одинаковой скоростью, равной 1. Для добавления интриги каждому из них назначили случайное время старта $$$t_i$$$ так, что внутри одной команды лыжники с меньшими номерами стартуют раньше лыжников с большими номерами, то есть верно, что $$$t_1 \lt t_3 \lt t_5 \lt \ldots \lt t_{2n - 1}$$$ и $$$t_2 \lt t_4 \lt t_6 \lt \ldots \lt t_{2n}$$$. Кроме того, выполняется условие $$$t_1 \leq t_2$$$, то есть первый из команды A стартует не позже первого из команды B.

Первый лыжник из команды A стартует с эстафетным флажком. Далее происходит следующее: лыжник, двигающийся с флажком, передаёт его первому встречному спортсмену из противоположной команды (если таковой имеется). Тот поступает точно так же. Это происходит до тех пор, пока кто-то из лыжников с флагом не прибежит в точку старта противоположной команды, не встретив ни одного соперника по пути, и тем самым не одержит победу. Телезрителей же волнует следующий вопрос: какое расстояние преодолеет флаг, прежде чем один из лыжников принесёт его в точку старта соперников?

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

В первой строке находится целое число $$$n$$$ – количество лыжников в каждой команде ($$$1 \leq n \leq 10^5$$$).

Во второй строке находится целое число $$$d$$$ – расстояние между пунктами $$$A$$$ и $$$B$$$ ($$$1 \leq d \leq 10^9$$$).

В следующих $$$n$$$ строках содержатся времена $$$t_i$$$ старта лыжников из команды $$$A$$$ ($$$0 \leq t_1 \lt t_3 \lt t_5 \lt \ldots \lt t_{2n - 1} \leq 10^9$$$).

В следующих $$$n$$$ строках содержатся времена $$$t_i$$$ старта лыжников из команды $$$B$$$ ($$$0 \leq t_2 \lt t_4 \lt t_6 \lt \ldots \lt t_{2n} \leq 10^9$$$).

Гарантируется, что $$$t_1 \leq t_2$$$.

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

Выведите одно число – расстояние, которое преодолеет эстафетный флаг, прежде чем один из лыжников принесёт его в противоположный пункт. Обратите внимание на то, что если флаг принесут в один из пунктов в тот момент, когда из этого пункта стартует очередной лыжник, – это считается победой, эстафета окончена. Входные данные подобраны таким образом, что ответом всегда является целое число.

Система оценки

Решения, правильно работающие при $$$n \leq 1000$$$, будут оцениваться в 40 баллов.

Примеры
Входные данные
5
5
0
3
7
8
14
2
3
11
13
20
Выходные данные
13
Входные данные
6
10
5
6
7
8
9
10
14
15
16
17
18
19
Выходные данные
24
Примечание

Проиллюстрируем развитие событий в первом примере.

В каждой команде по 5 лыжников. Расстояние между пунктами равно 5, для дальнейших рассуждений предположим, что пункт A находится в точке 0, а пункт B – в точке 5.

Лыжники команды A стартуют в моменты 0, 3, 7, 8, 14.

Лыжники команды B стартуют в моменты 2, 3, 11, 14, 20.

События следуют так:

момент 0 – старт лыжника 1 с флагом из пункта A;

момент 2 – старт лыжника 2 из пункта B;

момент 3 – старт лыжника 3 из пункта A и лыжника 4 из пункта B;

момент 3.5 – лыжники 1 и 2 встретятся в точке 3.5, флаг окажется у лыжника 2 (флаг сместился вправо на 3.5);

момент 5 – лыжники 3 и 2 встретятся в точке 2, флаг окажется у лыжника 3 (флаг сместился влево на 1.5);

момент 5.5 – лыжники 3 и 4 встретятся в точке 2.5, флаг окажется у лыжника 4 (флаг сместился вправо на 0.5);

момент 7 – старт лыжника 5 из пункта A;

момент 7.5 – лыжники 5 и 4 встретятся в точке 0.5, флаг окажется у лыжника 5 (флаг сместился влево на 2);

момент 8 – старт лыжника 7 из пункта A;

момент 11 – старт лыжника 6 из пункта B;

момент 11.5 – лыжники 5 и 6 встретятся в точке 4.5, флаг окажется у лыжника 6 (флаг сместился вправо на 4); момент 12 – лыжники 7 и 6 встретятся в точке 4, флаг окажется у лыжника 7 (флаг сместился влево на 0.5);

момент 13 – старт лыжника 8 из пункта B, но лыжник 7 в этот момент прибежит с флагом в пункт B и команда А победит (флаг сместился вправо на 1).

В итоге флаг проделал путь длиной 3.5 + 1.5 + 0.5 + 2 + 4 + 0.5 + 1 = 13.