Городские олимпиады/1-2 курсы/Предметная олимпиада по информатике 2019


7. Весенняя прогулка (150 баллов)

Автор задачи: Грудинин Владислав
Ограничение по времени: 1 с.
Ограничение по памяти: 256 МБ

Как известно, Виктор любить прогуляться по парку перед работой. Но вот незадача, наступила весна, и начал таять снег, тем самым затопляя на всю весну некоторые участки парка.

Парк представляет из себя n \times m квадратных участков. Свою прогулку Виктор начинает в левом нижнем углу, который имеет координаты (1, 1), а заканчивает в правом верхнем с координатами (n, m). Из текущего участка Виктор может перейти в любой не затопленный участок, который имеет смежную с текущим участком сторону.

Этой весной Виктор ходил на работу каждый день в течение k дней. Если он мог пройти через парк, то он так и поступал, в противном случае он искал обходной путь. У вас есть статистика коммунальной службы о затоплении парка этой весной, и вам стало интересно, сколько раз за всю весну Вите пришлось искать обходной путь.

Входные данные

В первой строке записаны три целых числа n, m и k — высота и ширина парка, а также количество дней в течении которых Виктор ходил на работу (2 \leqslant n, m \leqslant 100, 1 \leqslant k \leqslant 10^5).

В следующей строке записано одно целое число q — количество записей о затопленных участках (0 \leqslant q \leqslant n \cdot m - 2). Гарантируется, что начальная и конечная точка пути не были затоплены этой весной, а перед первым днём в парке не затоплен ни один участок.

В следующих q строках содержится по 3 целых числа x_i, y_i и d_i — координаты затопленного участка и день затопления (1 \leqslant x_i \leqslant n, 1 \leqslant y_i \leqslant m, 1 \leqslant d_i \leqslant k).

Выходные данные

Вывести одно целое число — количество дней, в которые Виктору приходилось искать обходной путь.

Примеры
Стандартный вводСтандартный вывод
3 3 10
3
1 2 3
2 2 3
2 1 3
8
3 3 10
3
1 2 1
2 2 1
2 1 1
10
5 5 100
5
1 2 10
4 3 12
1 5 97
2 4 98
3 4 50
0
Примечания

В этой задаче нет подзадач. Решения участников будут проверяться на наборе из 25 тестов, за прохождение каждого из которых будет начислено 6 баллов.