Андроид Андреид — известный на всю галактику детектив. Сейчас он расследует дело о вандализме на выставке современного искусства.
Главный экспонат выставки — конструкция из n матрешек — кукол, которые можно вкладывать друг в друга. Матрешки пронумерованы от 1 до n. Матрешку с меньшим номером можно вложить в матрешку с большим номером, при этом две матрешки не могут вкладываться непосредственно в одну и ту же матрешку, но возможны цепочки вложения, например, 1 → 2 → 4 → 5.
За одну секунду можно произвести любую из двух следующих операций.
- Если есть матрёшка a, никуда не вложенная, и матрёшка b, причём b не содержит никаких матрёшек и не вложена ни в какую другую матрёшку, можно поместить a в b;
- Если матрёшка a непосредственно содержится в матрёшке b, причём b не вложена ни в какую другую матрёшку, можно достать a из b.
Согласно современным эстетическим нормам матрешки на выставке были собраны в определенной конфигурации, то есть в виде нескольких отдельных цепочек вложенных матрёшек, однако преступник, следуя загадочному плану, разобрал все матрёшки и собрал их в одну большую цепочку (1 → 2 → ... → n). Для продолжения расследования Андреиду необходимо узнать, за какое минимальное время это возможно сделать.
Выходные данные
В единственной строке выведите минимальное количество секунд, за которое можно из изначальной конфигурации собрать одну большую цепочку.
Примечание
В первом тесте из условия есть две цепочки: 1 → 2 и 3. За одну секунду можно вложить первую цепочку во вторую и получить 1 → 2 → 3.
Во втором тесте из условия требуется разобрать все три цепочки на отдельные матрёшки за 2 + 1 + 1 = 4 секунды, и собрать из них одну большую цепочку за 6 секунд.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
2 1 2
1 3
|
1
|
|
2
|
7 3
3 1 3 7
2 2 5
2 4 6
|
10
|