Сегодня трудно удивить телезрителей известными видами спорта. Организаторы одного из зимних соревнований решили провести лыжную эстафету в новом формате: лыжники бегут не друг за другом, а друг навстречу другу.
Есть две команды, в каждой по $$$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 баллов.
5503781423111320
13
6105678910141516171819
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.
