UOJ Logo

NOI.AC

1S 512MB

#1666. Gakkipan的房子

Statistics

题目描述

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