小L的扩展
题号：NC311991
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}小 L 的科研毫无进展，于是他开始在纸上画方格。
\hspace{15pt}小 L 的纸由 n 行 m 列共 n\times m 个白色方格组成，其中有 a 个方格被染黑了，染黑的方格每个单位时间会向上下左右四个方向扩散一格。其中有 b 个方格上有蓝色的墨水，每个染上蓝色的墨水的方格会在某个特定的时间点变为白色，在蓝色墨水存在的时刻是不能被染黑的方格扩散到的。
\hspace{15pt}小 L 想知道这张纸上的方格什么时候被完全染黑，请你帮帮他。

\hspace{15pt}更具体地：
\hspace{23pt}\bullet\,记初始时刻为 0，给出的 a 个格子在时刻 0 已经是黑色；给出的 b 个格子从时刻 0 起为蓝色，直到时刻 t_j 到来时先变为白色。
\hspace{23pt}\bullet\,对每个整数时刻 t=1,2,3,\dots，先让所有满足 t_j=t 的蓝色方格变为白色，然后黑色从所有已变黑的方格向上下左右四邻方格各扩散 1 格；若目标方格在该时刻已为白色，则在该时刻被染黑。

输入描述:

\hspace{15pt}第一行输入四个正整数 n,m,a,b \left(1\le n\times m\le 10^6;\, 1\le a,b,a+b\le n\times m\right)，表示纸张大小、黑方格个数、蓝方格个数。
\hspace{15pt}此后 a 行，第 i 行输入两个正整数 x_i,y_i \left(1\le x_i\le n;\, 1\le y_i\le m\right)，表示第 i 个黑方格的位置；
\hspace{15pt}此后 b 行，第 j 行输入三个正整数 x_j,y_j,t_j \left(1\le x_j\le n;\, 1\le y_j\le m;\, 1\le t_j \le 10^9\right)，表示第 j 个蓝方格的位置及其变为白色的时间。
\hspace{15pt}保证 a+b 个被染色的方格两两不同，即不存在同一个方格既被染黑又被染蓝。

输出描述:

\hspace{15pt}输出一个整数，表示整张纸被完全染黑的时间。
示例1

输入

复制 
3 3 1 1
1 1
1 2 5

输出

复制 
5
示例2

输入

复制 
2 4 2 1
1 1
2 4
1 2 100

输出

复制 
100
示例3

输入

复制 
2 4 1 1
1 1
1 2 4

输出

复制 
5