题目描述

Gakkipan有一天捡到了阿拉丁神灯，就想在一块n×m的土地上建造一块属于自己的房子，大小为k×k，但是需要k×k的地基才能建造，
于是阿拉丁决定刁难一下Gakkipan，每次只会随机地在(x_i, y_i)处打造一块地基，时间也是随机在第t_i秒，也就是说出现一块k×k的地基
时间早晚，全凭人品！现在Gakkipan就想知道自己最早何时能有一块k×k的地基来建造房子

文件输入

第一行4个数n m k q表示土地的长为n，宽为m，地基大小为 k×k， 有q次随机操作
然后有q行，每行3个数x_i, y_i, t_i表示，在第t_i秒，(x_i, y_i)的地基建造完成

文件输出

输出最小的秒数t，使得在t时刻，刚好有一块k×k的地基
同时因为运气不好，也可能q次随机并没有产生k×k的地基，则输出-1

输入样例

2 3 2 5
2 1 8
2 2 8
1 2 1
1 3 4
2 3 2

输出样例

8

数据规模

对于所有的数据，1 <= x_i <= n,  1 <= y_i <= m,   1 <= t_i <= 1000000000, 1 <= k <= min(n, m),  0 <= q <= n * m  
对于20%的数据,  n, m <= 50, q <= 100
对于40%的数据,  n, m <= 100, q <= 1000
对于60%的数据,  n, m <= 100, q <= 10000 
对于100%的数据, n, m <= 500, q <= 100000