Вы находитесь на острове, который можно представить как таблицу \(n \times m\). Строки таблицы пронумерованы целыми числами от \(1\) до \(n\), а столбцы пронумерованы целыми числами от \(1\) до \(m\). На острове расположено \(k\) сокровищ, \(i\)-е из которых находится в клетке \((r_i, c_i)\).
Изначально вы находитесь в нижней левой клетке острова, в клетке \((1, 1)\). Если вы окажетесь в одной клетке с сокровищем, то вы можете забрать его, не тратя дополнительного времени. За один ход вы можете переместится вверх (из \((r, c)\) в \((r+1, c)\)), налево (из \((r, c)\) в \((r, c-1)\)) или направо (из \((r, c)\) в \((r, c+1)\)). Из-за ловушек вы не можете двигаться вниз.
Однако двигаться вверх тоже небезопасно. Вы можете двигаться вверх, только если вы находитесь в безопасном столбце. Есть \(q\) безопасных столбцов: \(b_1, b_2, \ldots, b_q\). Вы хотите собрать все сокровища как можно быстрее. Выясните минимальное число ходов, за которое это можно сделать.
Выходные данные
Выведите минимальное число ходов, которое нужно, чтобы собрать все сокровища.
Примечание
В первом примере следует двигаться вверх во втором столбце, собирая в каждой строке сокровища, расположенные в первом столбце.
Во втором примере следует идти вверх в первом столбце.
В третьем примере оптимально собрать сокровище в клетке \((1;6)\), затем переместиться вверх в строку \(2\), используя столбец \(6\), затем собрать сокровище в клетке \((2;2)\), подняться в верхний ряд, используя столбец \(1\), и собрать последнее сокровище в клетке \((3;4)\). Всего \(15\) ходов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 3 2
1 1
2 1
3 1
2 3
|
6
|
|
2
|
3 5 3 2
1 2
2 3
3 1
1 5
|
8
|
|
3
|
3 6 3 2
1 6
2 2
3 4
1 6
|
15
|