Знаменитый искатель приключений Индиана Джонс попал в ловушку! Он оказался заперт в прямоугольной комнате размером N × M, пол которой разделён на квадратные клетки 1 × 1. По вертикали клетки комнаты нумеруются от 1 до N сверху вниз, по горизонтали — от 1 до M слева направо.
На каждой из клеток пола нарисована цифра от 1 до 9. Индиана Джонс моментально сообразил, что эти цифры означают не что иное, как период срабатывания встроенных в пол горелок: каждую секунду, номер которой делится на изображённое на клетке число, из отверстий в полу бьют мощные языки пламени, причиняющие одну единицу урона, если на них наступить.
Изначально (в первую секунду) Индиана Джонс стоит в клетке (1; 1). В каждую следующую секунду он может либо остаться стоять в текущей клетке, либо перешагнуть в любую из клеток, имеющих общую сторону с текущей. В клетке (N; M) проделан люк, ведущий на свободу.
Цель Индианы Джонса — добраться до выхода, получив по пути минимальное количество урона. Но ему надо действовать быстро, так как по прошествии T секунд вся комната самоуничтожится.
Подскажите ему, как выбраться из ловушки с наименьшими потерями.
Первая строка содержит целые числа N, M и T (1 ≤ N, M ≤ 50, 1 ≤ T ≤ 400) — соответственно размеры комнаты и количество секунд, оставшееся до её разрушения.
Следующие N строк описывают клетки комнаты. i-я из них содержит строку из M цифр Aij (1 ≤ Aij ≤ 9), j-я из которых равна периоду срабатывания горелок в клетке (i; j).
Выведите одно целое число — минимальное количество единиц урона, которое может получить Индиана Джонс, оказавшись в клетке с выходом не позже секунды T. Обратите внимание, что Индиана Джонс может получить урон и в стартовой клетке, и в клетке с выходом.
Если Индиана Джонс не успеет добраться до выхода, выведите число -1.
## Входные Данные
Первая строка содержит целые числа N, M и T (1 ≤ N, M ≤ 50, 1 ≤ T ≤ 400) — соответственно размеры комнаты и количество секунд, оставшееся до её разрушения.Следующие N строк описывают клетки комнаты. i-я из них содержит строку из M цифр Aij (1 ≤ Aij ≤ 9), j-я из которых равна периоду срабатывания горелок в клетке (i; j).
## Выходные Данные
Выведите одно целое число — минимальное количество единиц урона, которое может получить Индиана Джонс, оказавшись в клетке с выходом не позже секунды T. Обратите внимание, что Индиана Джонс может получить урон и в стартовой клетке, и в клетке с выходом.Если Индиана Джонс не успеет добраться до выхода, выведите число -1.
## Примеры
Входные данные3 4 8322432431131Выходные данные1Входные данные3 4 6322432431131Выходные данные2
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the total number of managers.
Let $ m \in \mathbb{Z}_{\geq 0} $ be the number of managers who require document revision.
Let $ K = \{k_1, k_2, \dots, k_m\} \subseteq \{1, 2, \dots, n\} $ with $ k_1 < k_2 < \dots < k_m $ be the set of managers who alternate between rejecting (odd visits) and approving (even visits).
Let $ R = \{1, 2, \dots, n\} \setminus K $ be the set of managers who approve the document on every visit.
**Constraints**
1. $ 1 \leq n \leq 30 $
2. $ 0 \leq m \leq n $
3. For all $ i \in \{1, \dots, m\} $: $ 1 \leq k_i \leq n $, and $ k_i $ are strictly increasing.
**Objective**
Simulate the sequential approval process:
- The document is processed in order from manager $ 1 $ to $ n $.
- For manager $ i \in K $:
- On the $ j $-th visit (counting total times the document reaches $ i $):
- If $ j $ is odd → reject (restart from manager 1).
- If $ j $ is even → approve.
- For manager $ i \in R $: approve on first and all subsequent visits.
- Only one manager’s decision is processed per day.
- The process ends when all $ n $ managers have approved the document.
Compute the total number of days required until the document is fully signed.