Statement is not available in English language
C. Вывоз мусора
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вчера кот Бенедикт целый день мог наблюдать из окна, как работники парка собирают опавшую листву и ветки и складывают их в специальные мешки. Мешки были сложены вдоль узкой аллеи, и сегодня приехали их забирать. Вдоль узкой прямой аллеи едет маленький погрузчик и собирает мешки в ковш. В некоторых местах с аллеи есть выезды на широкую дорогу. Когда погрузчик набирает в ковш $$$k$$$ мешков, он отправляется к ближайшему выезду и сбрасывает эти мешки в кузов большого грузовика.

В случае, если погрузчик находится на равном расстоянии от двух выездов, он выбирает выезд с большей координатой.

Разумеется, погрузчик отвезет последнюю партию мешков к большому грузовику, даже если мешков будет меньше $$$k$$$.

Вам известны координаты всех $$$n$$$ мешков с мусором и всех $$$m$$$ выездов на широкую дорогу. Погрузчик собирает мешки строго в порядке их появления в исходных данных.

Ваша задача — определить расстояние, которое придётся проехать погрузчику, чтобы поместить все мешки с мусором в кузов грузовика.

Изначально погрузчик находится в точке с координатой $$$0$$$. Расстояние, которое погрузчик проезжает по выезду с аллеи на дорогу (или обратно) равно $$$1$$$.

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

В первой строке содержится целое число $$$k$$$ $$$(1 \le k \le 10^5)$$$ — количество мешков, которые могут поместиться в ковш погрузчика.

Во второй строке содержится целое число $$$m$$$ $$$(1 \le m \le 10^5)$$$ — количество выездов с аллеи.

В каждой из следующих $$$m$$$ строк содержится по одному целому числу $$$c_j$$$ $$$(0 \le c_j \le 10^9, \, j = 1, 2, \ldots, m)$$$ — координате выезда с аллеи.

Гарантируется, что $$$c_1 \lt c_2 \lt \ldots \lt c_m$$$.

В следующей строке содержится целое число $$$n$$$ $$$(1 \le n \le 10^5)$$$ — количество мешков с мусором.

В каждой из следующих $$$n$$$ строк содержится по одному целому числу $$$b_i$$$ $$$(0 \le b_i \le 10^9, \, i = 1, 2, \ldots, n)$$$ — координате очередного мешка с мусором.

Гарантируется, что $$$b_1 \le b_2 \le \ldots \le b_n$$$.

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

Выведите единственное целое число — расстояние, которое понадобится проехать погрузчику, чтобы поместить все мешки с мусором в кузов грузовика.

Обратите внимание, что ответ может превышать возможное значение $$$32$$$-битной целочисленной переменной, поэтому необходимо использовать $$$64$$$-битные целочисленные типы данных (тип $$$int64$$$ в языке $$$Pascal$$$, тип $$$long \, long$$$ в $$$C++$$$, тип $$$long$$$ в $$$Java$$$ и $$$C\#$$$).

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

В первых двух подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.

В третьей подзадаче баллы начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены.

Для второй и третьей подзадач требуется, чтобы программа верно решала предшествующие подзадачи. Более подробно разбиение на подзадачи показано в таблице ниже.

ПодзадачаБаллы за тестОграниченияНеобходимыеИнформация
(баллыподзадачио проверке
за подзадачу)
13 (до 30)$$$n, \, m \le 1000$$$нетполная
23 (до 30)$$$n, \, m \le 10^5, \, k \ge 10$$$,1полная
30 (40)любые допустимые значения1,2первая ошибка

Пример
Входные данные
2
4
0
12
18
25
15
3
4
4
4
4
6
6
6
13
16
16
18
19
21
21
Выходные данные
77
Примечание

Поясним приведённый пример.

В ковш погрузчика помещается $$$k = 2$$$ мешка с мусором.

Выездов на широкую дорогу $$$4$$$, они имеют координаты $$$0$$$, $$$12$$$, $$$18$$$ и $$$25$$$.

Мешков с мусором всего $$$n = 15$$$, имеют координаты $$$3$$$, $$$4$$$, $$$4$$$, $$$4$$$, $$$4$$$, $$$6$$$, $$$6$$$, $$$6$$$, $$$13$$$, $$$16$$$, $$$16$$$, $$$18$$$, $$$19$$$, $$$21$$$, $$$21$$$.

Сначала погрузчик (стартуя из точки $$$0$$$) отправляется в точку с координатой $$$3$$$ и забирает там единственный мешок. Затем он переезжает в точку $$$4$$$ и забирает один из $$$4$$$ мешков, находящихся в этой точке. Ближайший выезд находится в точке $$$0$$$, поэтому погрузчик отвозит мешки туда. Сразу после выгрузки мешков проделанный им путь равен $$$9$$$ ($$$4$$$ до более дальнего мешка, столько же обратно и $$$1$$$ по выезду).

Затем погрузчик заберёт ещё два мешка из этой же точки $$$4$$$ ($$$1$$$ по выезду, $$$4$$$ до мешков, $$$4$$$ обратно, ещё $$$1$$$ по выезду). Суммарный путь становится равным $$$19$$$ (в момент выгрузки).

После этого погрузчик отправится за последним мешком в точке $$$4$$$, проедет в точку $$$6$$$ и заберёт один мешок из этой точки. Расстояния от точки $$$6$$$ до выезда с координатой $$$0$$$ и до выезда с координатой $$$12$$$ одинаковые; по условию задачи погрузчик отправится к выезду с большей координатой. Суммарный путь составит $$$19 + 1 + 12 + 1 = 33$$$ к моменту выгрузки.

Затем погрузчик вернётся в точку $$$6$$$ и отвезёт ещё два мешка. Суммарный путь в момент их выгрузки будет $$$33 + 1 + 6 + 6 + 1 = 47$$$.

Следующая точка, к которой поедет погрузчик, имеет координату $$$13$$$. В этой точке он заберёт один мешок и отправится в точку $$$16$$$, где заберёт ещё один мешок. Ближайший выезд находится в точке $$$18$$$, поэтому к моменту выгрузки этих мешков суммарный путь составит $$$47 + 1 + 6 + 1 = 55$$$.

Теперь погрузчику придётся вернуться в точку $$$16$$$, чтобы забрать там оставшийся мешок, а затем отправиться в точку $$$18$$$, чтобы забрать ещё один мешок и отвезти его к грузовику. Суммарный путь в момент выгрузки этих мешков будет $$$55 + 1 + 2 + 2 + 1 = 61$$$.

После этого погрузчик поедет сначала в точку $$$19$$$, а затем в точку $$$21$$$ и заберёт в ковш по одному мешку в каждой точке. Ближайшим выездом к точке $$$21$$$ является выезд в точке $$$18$$$, так что суммарный путь к моменту выгрузки этих мешков составит $$$61 + 1 + 3 + 3 + 1 = 69$$$.

Наконец, погрузчик отправится в точку $$$21$$$ за последним мешком и отвезёт его через выезд в точке $$$18$$$. Суммарный путь, который проделает погрузчик к моменту выгрузки этого мешка, составит $$$69 + 1 + 3 + 3 + 1 = 77$$$. Это число и будет ответом.