Ух і сусіди

Сусіди знову котять бочку на Себека і придумують йому нові випробування. Цього разу у них є відрізок довжиною $n$. Сусіди помістили Себека в точку з координатою $0$ і сказали йому прострибати до точки з координатою $n$.

Але у Себека є проблема. Він може стрибати лише вперед на довжину $1$, $2$ або $3$. Проте сусіди вирішили ще більше його обмежити. Вони дали йому рядок $s$ довжиною $m$, що складається з малих латинських літер. Себек може стрибати вперед на довжину $x$ ($1\le x\le 3$), якщо у рядку $s$ є підрядок, для якого виконуються наступні умови:

1. Підрядок має довжину $x$.

2. Усі літери однакові.

3. Зліва від підрядка знаходиться буква, якої немає у підрядку, або такої букви немає взагалі (підрядок знаходиться скраю).

4. Справа від підрядка знаходиться буква, якої немає у підрядку, або такої букви немає взагалі.

Рядок $a$ називається підрядком $b$, якщо можна отримати $a$ з $b$, видаляючи кілька (можливо, жодного або всі) символів з початку і кілька (можливо, жодного або всі) символів з кінця.

Наприклад, нехай є рядок «aabaaabbcbbbebbab» та $x=2$. Тоді у рядку є кілька підрядків, які підходять під обмеження: «(aa)baaa(bb)cbbbe(bb)ab». Тому у цьому випадку можна стрибати на довжину $2$. Крім цього, цей рядок дозволяє стрибати також і на довжини $1$ і $3$. А от рядок «ebbbcedddd» дозволяє стрибати лише на довжини $1$ і $3$.

Себеку треба, стрибаючи тільки на дозволену довжину вперед, з точки $0$ потрапити у точку з координатою $n$ за мінімальну кількість стрибків. Уявіть, що ви Себек, і порахуйте цю мінімальну кількість стрибків.

Зверніть увагу, що Себеку потрібно потрапити саме у точку з координатою $n$, а не $n+1$ чи $n+2$.

Input

Перший рядок містить одне ціле число $n$ ($1\le n\le 1000000000$) — довжина відрізка, по якій стрибає Себек.

Другий рядок містить одне ціле число $m$ ($1\le m\le 200000$) — довжина рядка сусідів.

Третій рядок містить рядок $s$ довжиною $m$, що складається з малих латинських літер — рядок сусідів.

Output

Виведіть одне ціле число — мінімальну кількість стрибків, що потрібно зробити Себеку, щоб потрапити в точку з координатою $n$, починаючи з точки з координатою $0$. Якщо він це зробити не може, то виведіть $-1$.

Examples

Note

1. Себек може стрибати на $1$ і $3$. Можливий варіант стрибків $1+3=4$

2. Себек може стрибати на $1$ і $3$. Можливий варіант стрибків $1+3+3+1+3=11$

3. Себек не може стрибати взагалі, бо єдиний підрядок з однакових літер має довжину $5$.