Недавно девочка Люба купила себе новый монитор. Монитор представляет из себя прямоугольную матрицу размера n × m. Но прошло какое-то время, и она стала замечать, что некоторые пиксели в нём начали ломаться. Люба для себя решила, что монитор сломается в первый момент времени, когда в нём будет окно размера хотя бы k × k, полностью состоящее из сломанных пикселей. Она знает, что всего сломалось q пикселей, а также знает, в какой момент времени какой пиксель сломается. Помогите Любе найти момент времени, когда монитор сломается, либо сообщите, что такой момент не настанет даже после поломки q пикселей.
Выходные данные
Выведите единственное число — момент времени, когда монитор сломается, или "-1", если монитор после поломки q пикселей не окажется сломанным.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3 2 5
2 1 8
2 2 8
1 2 1
1 3 4
2 3 2
|
8
|
|
2
|
3 3 2 5
1 2 2
2 2 1
2 3 5
3 2 10
2 1 100
|
-1
|