Безумный ученый Майк не использует медленные жесткие диски. В его модификации жесткого диска есть не одна, а n разных головок, которые могут читать данные параллельно.
Разрез жесткого диска Майка представляет собой бесконечный массив из дорожек. Дорожки массива пронумерованы слева направо целыми числами, начиная с 1. В начальном состоянии i-тая считывающая головка находится над дорожкой с номером hi. Программное обеспечение жесткого диска за 1 секунду может переместить каждую из головок ровно на одну дорожку направо или налево, либо оставить на текущей дорожке. В течение времени работы жесткого диска движение каждой головки не влияет на движение остальных головок: головки могут меняться местами; на каждой дорожке может находиться несколько головок. Дорожка считается считанной, если хотя бы одна головка побывала на этой дорожке. В частности, все дорожки под номерами h1, h2, ..., hn уже считаны в начале работы жесткого диска.
Майку нужно считать данные на m разных дорожках под номерами p1, p2, ..., pm. Определите наименьшее время, за которое жесткий диск сможет считать данные с заданных дорожек. Обратите внимание на то, что при этом дополнительно может быть считано произвольное количество других дорожек.
Выходные данные
Выведите единственное целое число — наименьшее время в секундах, за которое можно считать все нужные дорожки.
Примечание
Первый тест совпадает с рисунком. В данном случае данные дорожки можно считать за 2 секунды следующим образом:
- за первую секунду переместить 1-ую головку налево и на следующей секунде оставить ее на месте;
- вторую головку два раза переместить налево;
- третью головку два раза переместить направо (причем 6-ая дорожка считана уже в самом начале работы диска).
За 1 секунду дорожки считать невозможно, так как 3-я головка находится на расстоянии 2 от 8-ой дорожки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
2 5 6
1 3 6 8
|
2
|
|
2
|
3 3
1 2 3
1 2 3
|
0
|
|
3
|
1 2
165
142 200
|
81
|