e-olymp
Competitions

ІІІ етап Всеукраїнської олімпіади з інформатик в Житомирській обл. 2019-2020

Лісові пожежі

Глобальне потепління призводить до високої пожежної небезпеки. З метою своєчасного реагування у випадку загоряння лісу, Микола Петрович хоче змоделювати розповсюдження ймовірної лісової пожежі.

Відомо, що ліс має прямокутну форму розміром N x M і розбитий на одиничні квадрати. Для кожного квадрату задано кількість хвилин, за яку квадрат повністю вигорає. Після повного вигорання квадрату пожежа миттєво переходить до суміжних квадратів (по горизонталі, по вертикалі та по діагоналі), які ще не згоріли або на даний момент не горять.

Відомі координати місць загоряння. Допоможіть Миколі Петровичу порахувати, через скільки хвилин пожежа досягне вказаного квадрату.

Вхідні дані.

В першому рядку записані 5 цілих чисел N, M, K, X, Y, де N та M – розміри місцевості, K – кількість місць загоряння, X, Y – координати квадрату, для якого потрібно визначити час досягнення пожежі.

В наступних N рядках знаходяться по M чисел – кількість часу на повне вигорання відповідного квадрату місцевості.

Наступні К рядків – координати місць загоряння.

Всі числа натуральні, менші або рівні 150.

Вихідні дані.

Ціле число – кількість часу, через який пожежа перейде до квадрату X, Y. Z2_4.jpg

Time limit 1 second
Memory limit 64 MiB
Input example #1
5 4 1 4 4
1 2 5 1
1 2 3 1
1 1 1 6
1 1 6 6
1 1 1 1
1 1
Output example #1
4