/ 
実行時間制限: 3 sec / メモリ制限: 1024 MiB
問題文
2 次元平面上に、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
- 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) を (2,2)（下図の星）に配置することで、(x_1,y_1) と原点のマンハッタン距離を 4 にすることができます。
他にも、例えば (x_1,y_1) を (1.5, 2.5) に配置しても条件を満たし、原点とのマンハッタン距離を 4 にすることができます。
入力例 2
2 1 2 1 1 2 -2 2 3 1 2 1
出力例 2
3
例えば、(x_1,y_1) を (0,2)、(x_2,y_2) を (-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 以下にすることができません。
Problem Statement
Consider placing N points \{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\} on a two-dimensional plane subject to the following conditions:
- For all i=1,2,\dots,N, the Manhattan distance between point (x_i,y_i) and (a_i,b_i) is at most d_i.
- For all j=1,2,\dots,M, the Manhattan distance between point (x_{u_j},y_{u_j}) and (x_{v_j},y_{v_j}) is at most e_j.
Here, the Manhattan distance between two points (p_1,q_1) and (p_2,q_2) is defined as |p_1-p_2|+|q_1-q_2|. Note that the coordinates x_i and y_i are not necessarily integers.
Determine if there exists such a placement of N (not necessarily distinct) points. If it exists, find the maximum possible Manhattan distance between the origin (0,0) and point (x_P,y_P). Under the constraints of this problem, the answer can be proven an integer, so print the answer as an integer.
Constraints
- 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, then (u_j,v_j) \neq (u_k,v_k).
- 0 \leq e_j\leq 10^8
- All input values are integers.
Input
The input is given from Standard Input in the following format:
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
Output
Print -1 if there is no conforming placement.
If there is, print the maximum possible Manhattan distance between the origin (0,0) and point (x_P,y_P) as an integer.
Sample Input 1
1 0 1 1 1 2
Sample Output 1
4
The setting of this sample is shown in the figure below. The circle denotes point (a_1,b_1), and the square denotes the region that satisfies |x-a_1|+|y-b_1|\leq d_1. For example, by placing (x_1,y_1) at (2,2) (the star in the figure), the Manhattan distance between (x_1,y_1) and the origin can be 4.
Alternatively, placing (x_1,y_1) at (1.5, 2.5) also satisfies the conditions, resulting in the Manhattan distance of 4.
Sample Input 2
2 1 2 1 1 2 -2 2 3 1 2 1
Sample Output 2
3
For example, by placing (x_1,y_1) at (0,2) and (x_2,y_2) at (-1,2), all the conditions can be satisfied. In this case, the Manhattan distance between (x_2,y_2) and the origin is 3, which is maximum possible.
Sample Input 3
2 1 1 2 0 1 -2 0 1 1 2 1
Sample Output 3
-1
No matter where you place (x_1,y_1) and (x_2,y_2) in the blue and orange regions, respectively, the Manhattan distance between them can never be 1.