14 грудня проводиться районна олімпіада з інформатики.

Завдання можна прочитати тут...

Задача D. «Penaltie»

Розглянемо таку гру. Нехай у нас є таблиця розміром M x N (M,N<101), в якій кожна клітинка має свою невід’ємну вартість, що не перевищує 100 у.о. На початку гри гравець знаходиться у верхній лівій клітинці та має K (K<=10000) у.о. і йому треба пройти у праву нижню клітинку. Черговий хід гравець може зробити лише направо або вниз. Якщо він перемістився у чергову клітинку, то він має заплатити штраф у розмірі, що зазначений на даній клітинці. Попробуйте знайти найбільшу суму грошей, яка може залишитися у гравця після того, як він досягне фінішної клітини або виведіть -1, якщо грошей на штрафи не вистачить.

Формат вхідних даних.  У вхідному файлі перший рядок містить цілі M, N, K. У наступних M рядка міститься по N цілих додатних чисел, що визначають розміри штрафів. 

Формат вихідних даних. У вихідний файл виведіть залишок грошей г ... Читати далі »