问题陈述
考虑放置 N 点 \{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\} 在二维平面上满足以下条件:
- 对于所有 i=1,2,\dots,N, 曼哈顿距离 点之间 (x_i,y_i) 和 (a_i,b_i) 最多是 d_i.
- 对于所有 j=1,2,\dots,M,点之间的曼哈顿距离 (x_{u_j},y_{u_j}) 和 (x_{v_j},y_{v_j}) 最多是 e_j.
这里,两点之间的曼哈顿距离 (p_1,q_1) 和 (p_2,q_2) 定义为 |p_1-p_2|+|q_1-q_2|。注意坐标 x_i 和 y_i 不一定是整数。
判断是否存在这样的放置 N (不一定不同)点。如果存在,求原点之间最大可能的曼哈顿距离 (0,0) 和点 (x_P,y_P)。 在该问题的约束下,可以证明答案是整数,因此将答案打印为整数。
约束
- 1 \leq N \leq 2000
- 0 \leq M \leq \min\{2000, N(N-1)/2\}
- 1 \leq P \leq N
- |a_i|,|b_i|\leq 10^8
- 0 \leq d_i\leq 10^8
- 1 \leq u_j < v_j\leq N
- If j\neq k,然后 (u_j,v_j) \neq (u_k,v_k).
- 0 \leq e_j\leq 10^8
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M P a_1 b_1 d_1 a_2 b_2 d_2 \vdots a_N b_N d_N u_1 v_1 e_1 u_2 v_2 e_2 \vdots u_M v_M e_M
输出
打印 -1 如果没有符合要求的放置。
如果有,则打印原点之间最大可能的曼哈顿距离 (0,0) 和点 (x_P,y_P) 作为整数。
示例输入 1
1 0 1 1 1 2
示例输出 1
4
该样本的设置如下图所示。 圆圈表示点 (a_1,b_1),正方形表示满足的区域 |x-a_1|+|y-b_1|\leq d_1。 例如,通过放置 (x_1,y_1) at (2,2) (图中的星星),曼哈顿距离 (x_1,y_1) 和原点可以是 4.

或者,放置 (x_1,y_1) at (1.5, 2.5) 也满足条件,导致曼哈顿距离为 4.
示例输入 2
2 1 2 1 1 2 -2 2 3 1 2 1
示例输出 2
3
例如,通过放置 (x_1,y_1) at (0,2) 和 (x_2,y_2) at (-1,2),所有条件都可以满足。 在这种情况下,曼哈顿距离 (x_2,y_2) 的原点是 3,这是最大可能的。

示例输入 3
2 1 1 2 0 1 -2 0 1 1 2 1
示例输出 3
-1
无论你放在哪里 (x_1,y_1) 和 (x_2,y_2) 分别在蓝色和橙色区域,它们之间的曼哈顿距离永远不可能 1.
