Задача: K-й путь
У вас есть таблица c N строками и M столбцами. В каждой ячейке таблицы записана одна строчная буква английского алфавита. Рассмотрим все возможные пути от левого верхнего угла до правого нижнего угла, если вам разрешено идти только вправо и вниз. Конкатенация букв в порядке обхода составляют строку. Скажем, что эта строка - значение пути. Теперь рассмотрим все такие пути и отсортируем их значения в алфавитном порядке. Ваша задача найти значение K-го пути в этом отсортированном листе.
Входные данные
В первой строке задается два целых числа N - количество рядов и M - количество столбцов заданной таблицы (1 <= N, M <= 30). Каждая из следующих N строк содержит ровно M строчных букв английского алфавита. Последняя строка входного файла содержит целое число K (1 <= K <= 1018). Гарантируется, что для K ответ всегда существует.
Выходные данные
Выведите ответ на задачу
Пояснения к примеру
abcdgk, abcdgk, abcdjk, abfdgk, abfdjk, abfijk, aefdgk, aefdjk, aefijk, aehijk
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3 4
abcd
efdg
hijk
4 |
abfdgk |
Ваш ответ: