{"problem":{"name":"F. Огненный лабиринт","description":{"content":"Знаменитый искатель приключений Индиана Джонс попал в ловушку! Он оказался заперт в прямоугольной комнате размером N × M, пол которой разделён на квадратные клетки 1 × 1. По вертикали клетки комнаты н","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10126F"},"statements":[{"statement_type":"Markdown","content":"Знаменитый искатель приключений Индиана Джонс попал в ловушку! Он оказался заперт в прямоугольной комнате размером N × M, пол которой разделён на квадратные клетки 1 × 1. По вертикали клетки комнаты нумеруются от 1 до N сверху вниз, по горизонтали — от 1 до M слева направо.\n\nНа каждой из клеток пола нарисована цифра от 1 до 9. Индиана Джонс моментально сообразил, что эти цифры означают не что иное, как период срабатывания встроенных в пол горелок: каждую секунду, номер которой делится на изображённое на клетке число, из отверстий в полу бьют мощные языки пламени, причиняющие одну единицу урона, если на них наступить.\n\nИзначально (в первую секунду) Индиана Джонс стоит в клетке (1; 1). В каждую следующую секунду он может либо остаться стоять в текущей клетке, либо перешагнуть в любую из клеток, имеющих общую сторону с текущей. В клетке (N; M) проделан люк, ведущий на свободу.\n\nЦель Индианы Джонса — добраться до выхода, получив по пути минимальное количество урона. Но ему надо действовать быстро, так как по прошествии T секунд вся комната самоуничтожится.\n\nПодскажите ему, как выбраться из ловушки с наименьшими потерями.\n\nПервая строка содержит целые числа N, M и T (1 ≤ N, M ≤ 50, 1 ≤ T ≤ 400) — соответственно размеры комнаты и количество секунд, оставшееся до её разрушения.\n\nСледующие N строк описывают клетки комнаты. i-я из них содержит строку из M цифр Aij (1 ≤ Aij ≤ 9), j-я из которых равна периоду срабатывания горелок в клетке (i; j).\n\nВыведите одно целое число — минимальное количество единиц урона, которое может получить Индиана Джонс, оказавшись в клетке с выходом не позже секунды T. Обратите внимание, что Индиана Джонс может получить урон и в стартовой клетке, и в клетке с выходом.\n\nЕсли Индиана Джонс не успеет добраться до выхода, выведите число -1.\n\n## Входные Данные\n\nПервая строка содержит целые числа N, M и T (1 ≤ N, M ≤ 50, 1 ≤ T ≤ 400) — соответственно размеры комнаты и количество секунд, оставшееся до её разрушения.Следующие N строк описывают клетки комнаты. i-я из них содержит строку из M цифр Aij (1 ≤ Aij ≤ 9), j-я из которых равна периоду срабатывания горелок в клетке (i; j).\n\n## Выходные Данные\n\nВыведите одно целое число — минимальное количество единиц урона, которое может получить Индиана Джонс, оказавшись в клетке с выходом не позже секунды T. Обратите внимание, что Индиана Джонс может получить урон и в стартовой клетке, и в клетке с выходом.Если Индиана Джонс не успеет добраться до выхода, выведите число -1.\n\n## Примеры\n\nВходные данные3 4 8322432431131Выходные данные1Входные данные3 4 6322432431131Выходные данные2\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the total number of managers.  \nLet $ m \\in \\mathbb{Z}_{\\geq 0} $ be the number of managers who require document revision.  \nLet $ 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).  \nLet $ R = \\{1, 2, \\dots, n\\} \\setminus K $ be the set of managers who approve the document on every visit.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 30 $  \n2. $ 0 \\leq m \\leq n $  \n3. For all $ i \\in \\{1, \\dots, m\\} $: $ 1 \\leq k_i \\leq n $, and $ k_i $ are strictly increasing.  \n\n**Objective**  \nSimulate the sequential approval process:  \n- The document is processed in order from manager $ 1 $ to $ n $.  \n- For manager $ i \\in K $:  \n  - On the $ j $-th visit (counting total times the document reaches $ i $):  \n    - If $ j $ is odd → reject (restart from manager 1).  \n    - If $ j $ is even → approve.  \n- For manager $ i \\in R $: approve on first and all subsequent visits.  \n- Only one manager’s decision is processed per day.  \n- The process ends when all $ n $ managers have approved the document.  \n\nCompute the total number of days required until the document is fully signed.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10126F","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}