Codes
Национална Олимпиада по Информатика 2013, Кръг 3
Time Limit: 1s, Memory Limit: 64MiB
Ели се опитва да отвори сейф. Той има клавиатура с цифри и съществува уникална K-цифрена комбинация (парола), която го отваря. Момичето знае за дребен дефект в сейфа - за да се отвори той е нужно единствено последните K въведени цифри да отговарят на отварящата го комбинация - без значение дали и ако да - какви цифри преди това е въвела тя.

Така, например, ако комбинацията за сейфа е "1337" и Ели е въвела "872135437421337", то той би се отворил след въвеждането на последната цифра. Забележете, че тази последователност от цифри би го отворила също и ако паролата беше, например, "8721", "4374", или "3742". За сметка на това не би се отворил ако комбинацията беше "8713". Накратко, сейфът се отваря единствено ако подстринг с дължина K на досега въведените цифри отговаря на секретния код.

Преди да се захване с тази задача, Ели се е сдобила със списък с N различни секретни комбинации с по K цифри, като знае, че истинската парола е една от тях. Помогнете й да генерира възможно по-къса последователност от цифри, която би отворила сейфа.
Вход
На първия ред на стандартния вход ще бъдат зададенди целите числа N и K - съответно броят възможни секретни комбинации и дължината на всяка от тях. Следват N реда, всеки съдържащ последователност от K на брой цифри '0'-'9'.
Изход
На единствен ред на стандартния изход изведете намерената от вас последователност.
Оценяване
Вашата програма ще бъде оценена на базата на това, колко дълга последователност сте намерили и дали тя наистина отваря сейфа. Ако някоя от дадените N възможни комбинации не се съдържа като подстринг, то вие ще получите 0 точки за съответния тест. В противен случай ще получите min(1, (authLen/yourLen)3) * 10 точки, където authLen е дължината на последователността, намерена от програмата на автора на задачата, yourLen е дължината на вашата последователност, а 10 са точките, предвидени за всеки тест.

Нека, например, намерената от автора последователност за примерния тест е с дължина 25. Изпечатаната на изхода последователност е с дължина 28. Следователно тя ще получи (25/28)3 * 10 = 7.117802 точки.

Забележете, че намерената от автора последователност не винаги ще е оптималната. В случай, че вашето решение намери по-добра, то ще получи пълния брой точки за съответния тест.
Ограничения
  • 1 ≤ K ≤ 6
  • 1 ≤ N ≤ 10,000
Примерен Вход Примерен Изход
9 4 1337 4242 1317 1713 7000 1314 1313 1717 0000 1337000042421317131413131717
Не е задължително изходната комбинация да е с минималната възможна дължина. В дадения пример съществуват и други последователности, които дават същия резултат, както и такива, които дават по-добър или по-лош. Пример за по-добро решение би било 13370000131717131314242 с дължина 23.
Мрън!