Чайная церемония – 2 (30 баллов)

Напомним, что произошло в предыдущей задаче

Маша и несколько ее подружек приготовили чай и кофе, стараясь выполнить пожелания всех гостей: кто-то захотел черный чай с лимоном, кто-то - зеленый чай, кто-то - кофе с парой ложечек сахара. Когда они расставили их на столе, оказалось, что немного перепутали, какой напиток перед кем именно следовало поставить.

Маша хотела сама переставить «неправильно» расставленные чашки. Однако гости решили, что проблема с неправильно расставленными чашками должна решаться иначе - чашки горячие, наполнены почти до краев, и переносить их сложно и долго: носить придется по одной чашке, медленно и осторожно. Будет проще, если чашки передавать от соседа к соседу.

Передача осуществляется следующим образом. Человек, перед которым стоит «неправильно» поставленная чашка, берет ее в руки и ставит ее перед одним из своих соседей (слева или справа). Такое перемещение чашки занимает V секунд. Считая, что перед одним человеком не может одновременно находиться более двух чашек, учитывая и ту, которую он держит в руках, найдите минимальное время, за которое все чашки можно переместить на «правильные» места.

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

Формат входного файла input.txt

Первая строка - целые числа G (1 <= G <= 20) - количество присутствующих и V (1 <= V <= 10) - время (в секундах), которое требуется, чтобы передать чашку соседу.

Вторая строка - G целых чисел (1 <= c1, c2, …, cG <= 20)через пробел. Каждое из чисел cK означает номер напитка, поставленного перед человеком № K. Напиток поставлен правильно, если cK = K (т.е. считается, что человек № K заказывал напиток № K).

Примечание.

Два человека считаются соседями, если их номера отличаются на 1. Также соседними считаются номера 1 и G.

Формат выходного файла output.txt

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

Пример входного файла

5 10

2 3 4 1 5

Пример выходного файла

20