D. Монитор
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно девочка Люба купила себе новый монитор. Монитор представляет из себя прямоугольную матрицу размера n × m. Но прошло какое-то время, и она стала замечать, что некоторые пиксели в нём начали ломаться. Люба для себя решила, что монитор сломается в первый момент времени, когда в нём будет окно размера хотя бы k × k, полностью состоящее из сломанных пикселей. Она знает, что всего сломалось q пикселей, а также знает, в какой момент времени какой пиксель сломается. Помогите Любе найти момент времени, когда монитор сломается, либо сообщите, что такой момент не настанет даже после поломки q пикселей.

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

В первой строке входных данных задано четыре целых числа n, m, k, q (1 ≤ n, m ≤ 500, 1 ≤ k ≤ min(n, m), 0 ≤ q ≤ n·m) — размеры монитора, размер окна, при поломке которого Люба будет считать монитор сломанным, и количество сломавшихся пикселей.

В следующих q строках содержится по 3 целых числа xi, yi, ti (1 ≤ xi ≤ n, 1 ≤ yi ≤ m, 0 ≤ t ≤ 109) — координаты i-го пикселя (его строка и столбец в матрице) и время его поломки. Гарантируется, что никакой пиксель не сломается дважды.

Также будем считать, что в секунду ti пиксель уже становится сломанным.

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

Выведите единственное число — момент времени, когда монитор сломается, или "-1", если монитор после поломки q пикселей не окажется сломанным.

Примеры
Входные данные
2 3 2 5
2 1 8
2 2 8
1 2 1
1 3 4
2 3 2
Выходные данные
8
Входные данные
3 3 2 5
1 2 2
2 2 1
2 3 5
3 2 10
2 1 100
Выходные данные
-1