Бајтленд е чудна земја: во неа има N градови поставени во линија, именувани А₁, А₂, … А_N. Во секој од овие градови има точно еден портал кој граѓаните на Бајтленд може да го користат за брзо патување кон другите градови.

Во Бајтленд постојат неколку различни типови на портали. Секој тип на портал е специјален и дозволува телепортирање само до портали од ист тип. Секое телепортирање се извршува за V часови.

Патувањето низ градовите во Бајтленд се одвива според следните правила:
- Од секој град A_i може да се стигне пешки до соседните градови А_i-1 и А_i+1 за 1 час.
- Од градот A_i кој има портал од тип Т може да се патува до кој било град кој исто така има портал од тип Т за V часови.

Формално, доколку некој се наоѓа во градот А_i, тој може да патува до соседните градови А_i-1 и А_i+1 за 1 час, или до кој било град A_j за кој важи дека Т_i = Т_j, за V часови.

Мендо се наоѓа во градот А₁ и сака да стигне до градот А_N за најкратко можно време. Помогнете му на Мендо да пресмета колку минимум часови му се потребни за да стигне од градот А₁ до градот А_N .

Влез

Во првиот ред се дадени два броја N и V (1 ≤ N ≤ 100 000, 0 ≤ V ≤ 100 000), кои ги означуваат бројот на градови, и бројот на часови кои се потребни за телепортирање меѓу два града со портал од ист тип.
Во вториот ред се дадени N броеви Т_i (1 ≤ Т_i ≤ 10), кои го означуваат типот на портал во секој од градовите, соодветно.

Забелешка:
За 15% од поените има најмногу 2 типови на портали т.е. Т_i≤2 за i=1..N.
Зa дополнителни 30% од поените, времето за телепортирање меѓу два града со портал од ист тип ќе биде 1 т.е. V = 1 и N ≤ 50.

Излез

Во првиот и единствен ред отпечатете го минималниот број на часови кои му се потребни на Мендо за да стигне од градот А₁ до градот А_N.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
5 1
3 2 1 3 1

излез
2

влез
20 2
2 1 3 4 6 8 5 7 4 2 3 5 2 1 3 4 3 5 6 7

излез
6

Објаснување за првиот тест пример: Мендо почнува во градот А₁; со помош на порталот тој пристигнува во градот А₄, и потоа од таму пешки пристигнува во крајниот град А₅. Пат: 1 (време = 0) -> 4 (време = 1) -> 5 (време = 2)
Објаснување за вториот тест пример: Пат: 1 (време = 0) -> 10 (време = 2) -> 9 (време = 3) -> 8 (време = 4) -> 20 (време = 6)