← 返回题目列表

Codeforces · 846/D

D. 监视器

中文机器翻译题面 查看原题

最近Luba买了一台显示器。监视器是一个大小为 n × m 的矩形矩阵。但后来她开始注意到一些像素无法正常工作。 Luba 认为,当显示器包含一个完全由损坏像素组成的 k × k 正方形时,显示器将在第一时间损坏。她知道 q 个像素已经损坏,并且对于每个像素,她都知道它停止工作的时刻。帮助 Luba 确定显示器何时损坏(或告知即使所有 q 像素停止工作后显示器仍未损坏)。

输入

第一行包含四个整数 n, m, k, q (1 ≤ n, m ≤ 500, 1 ≤ k ≤ min(n, m), 0 ≤ q ≤ n·m) — 显示器的长度和宽度,如果存在此尺寸的破损矩形,则显示器会破损的矩形的大小,以及破损像素的数量。

接下来的 q 行包含三个整数 xi, yi, ti (1 ≤ xi ≤ n, 1 ≤ yi ≤ m, 0 ≤ t ≤ 109) - 第 i 个损坏像素(矩阵中的行和列)的坐标以及它停止工作的时刻。每个像素最多列出一次。

我们认为像素在时刻 ti 已经损坏。

输出

打印一个数字 — 显示器损坏的最短时刻,如果在这 q 个像素停止工作后显示器仍未损坏,则打印“-1”。

示例

输入 #1

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

输出 #1

8

输入 #2

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

输出 #2

-1