Задача H. Мастер гирлянд ≡

Условие

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

Красивая последовательность лампочек представляет собой строку из латинских букв длины l.

Красивую последовательность можно добавить к гирлянде только тогда, когда гирлянда пуста или начало красивой последовательности совпадает с окончанием уже получившийся гирлянды: abab + abab + aber→ ababab + abe→ abababer.

Формат входных данных

Первая строка содержит два натуральных числа: N и L — количество красивых последовательностей и желаемая длина гирлянды. 1 ≤ N ≤ 300, 1 ≤ L ≤ 10000

Следующие N строк содержат длину красивой последовательности l_i и саму последовательность s_i. l_i ≤ 2000.

Каждая красивая последовательность лампочек не является подстрокой любой другой в этом наборе последовательностей. Так hello и hell не могут быть в одном наборе.

Формат выходных данных

Если возможно собрать гирлянду длины L из данных красивых последовательностей, то первая строка должна содержать целое число — количество красивых последовательностей лампочек в гирлянде и следующая за числом гирлянда.

Иначе вывести  − 1.

Если существует несколько решений выведите то, в котором наибольшее количество красивых последовательностей лампочек.

Примеры тестов

3 5
3 ror
2 er
3 rro

3
error