No submission language available for this problem.

题目描述

有一座 $n*m$ 平方米的私人果林，它的拥有者有一点点强迫症，他只在每平方米中间种果树。

当 $k*k$ 平方米内的每棵树的果子都成熟了，果林拥有者将会把这些果子树全砍了，果子拿去卖或酿果酒，树干当柴火或木料。

现在你是他的私人助理，需要你去计算，第一次可以去砍树的时间点。

输入格式

第一行 4 个整数 $n, m, k, q$

$(1 ≤ n, m ≤ 500, 1 ≤ k ≤ min(n, m), 0 ≤ q ≤ n·m)$

接下来有 $q$ 行，每行 3 个整数 $x_i, y_i, t_i$ 分别表示 第 i 棵树的位置以及它成熟的时间

输出格式

一个整数表示第一次可以去砍树的时间点。如果直到最后也无法砍树，输出 -1

样例 #1

样例输入 #1

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

样例输出 #1

8

样例 #2

样例输入 #2

3 3 2 5
1 2 2
2 2 1
2 3 5
3 2 10
2 1 100

样例输出 #2

-1

提示

$(1 ≤ x_i ≤ n, 1 ≤ y_i ≤ m, 0 ≤ t ≤ 10^9)$