Чайнворд

Обмеження: 2 сек., 256 МіБ

Чайнвордом називається лінійна послідовність клітинок, у які вписані задані слова так, щоб кожне наступне слово починалось літерою, якою закінчилось попереднє (ця літера записується лише раз). Слово можна використовувати в чайнворді неодноразово.

Кількість клітинок у чайнворді називається його довжиною (останні клітинки чайнворда можуть залишитись порожніми).

З можливих варіантів заповнення чайнворда треба вибрати тільки ті, у яких «заховане» задане гасло. Тобто задане гасло повинне бути підпослідовністю чайнворда.

Гасло формується з літер у довільних клітинках зліва направо. Наприклад, із слів: сон, навіс, орден, авто, нога можна побудувати 17-ти літерний чайнворд, що містить гасло весна : авторденавісонога.

Вхідні дані

У першому рядку задано гасло, що може мати до 30-ти символів.

У другому рядку задано два цілі числа: \(d\) — довжина чайнворда та \(n\) — кількість слів, які можна використати в цьому чайнворді.

У наступних \(n\) рядках задано слова, з яких треба сформувати чайнворд, що містить вказане гасло.

Вихідні дані

У єдиному рядку виведіть одне ціле число — кількість літер у найкоротшому чайнворді, який містить задане гасло.

Якщо чайнворд із «захованим» гаслом побудувати не можна, то слід вивести 0.

Обмеження

\(1 \le d \le 100\),

\(1 \le n \le 100\),

гасло та всі слова записані малими латинськими літерами та цифрами.

Приклади