A24218.Kingdom Game II

时间限制:5000ms
空间限制 512mb

Yuilice从梦中醒来，发现自己的王国$Yuilice-KingDom$被敌军入侵了，恼怒的Yuilice打开了O神，呼唤他的军团$Zhx$复制人军团支援战场。

现在我们可以将战场视为是一个$N \times N$的二维矩阵，由于Yuilice开启了O神，所以他发现地图上共有$M$支敌军，并且得知第$i$支敌军的位置处于下标为$x_i$与$y_i$的单元格上。

Yuilice一共呼唤了$K$支$Zhx$军团，其中第$i$支军团的初始所在地为$sx_i$与$sy_i$，同时因为传送门太小，导致第$i$支军团到达战场的时间为$t_i$秒。

敌军已经被O神的力量吓破了胆，不会移动。$Zhx$军团在每一秒会划分出四个子军团进行上下左右的移动剿灭敌军，同时被划分出来的子军团还可以继续划分，无穷无尽一直划分下去。

$Zhx$军团神挡杀神佛挡杀佛，所到之处的敌军灰飞烟灭，现在Yuilice困意上头，决定睡个回笼觉，他需要军师--也就是你，算出最少需要几秒才可以消灭所有的敌军？

第一行共输入三个整数$n,M,K$ - 代表地图大小与敌军军团数量、$Zhx$军团数量。

随后$M$行，每行输入$2$个整数$x_i$与$y_i$ - 代表第$i$支敌军的所在地。

随后$K$行，每行输入$3$个整数$sx_i、$$sy_i$与$t_i$ - 代表第$i$支$Zhx$军团的所在地与到达时间。

请输出一个整数代表最小需要的秒数。

【样例解释1】

在第$0$秒时，地图的$[3,3]$降临了一支Zhy军团，在第一秒时分出两个子军团前往$[3,2]$与$[2,3]$,在第二秒时候消灭了位于$[2,2]$的敌军，在第三秒划分出子军团前往$[1,2]$与$[2,1]$，于第四秒时消灭了位于$[1,1]$的敌军。

---

【样例解释2】

位于$[3,3]$降临的军队在第四秒消灭了所有敌军，但是$[1,1]$降临的军队还没有落地。

---

对于$50\%$的数据,$1 \leq n \leq 10 ,1 \leq M,K \leq n - 1, 1 \leq x_i,y_i,sx_i,sy_i \leq n , 0 \leq t_i \leq 10^3$

对于$100\%$的数据,$1 \leq n \leq 5 \times 10^3 ,1 \leq M,K \leq n - 1, 1 \leq x_i,y_i,sx_i,sy_i \leq n , 0 \leq t_i \leq 10^8$