AT_qupc2018_d Novelist

[problemUrl]: https://atcoder.jp/contests/qupc2018/tasks/qupc2018_d 異世界に転生した Treeone 君は冒険者として商人の護衛依頼を受けてお金を稼ぐことにしました。 転生先の高橋王国には王都以外に $ N $ 個の都市があり、各都市には $ 1,\ 2,\ ...,\ N $ と番号づけられています。王都と都市 $ i $ の間の移動には $ T_i $ 日かかります。 王都から王都以外の都市に向かう商人の護衛依頼が $ M $ 件あり、$ i $ 番目の依頼では王都を $ A_i $ 日目に出発し、都市 $ X_i $ に $ A_i\ +\ T_{X_i} $ 日目に到着します。 また、王都以外の都市から王都に向かう商人の護衛依頼が $ L $ 件あり、$ i $ 番目の依頼では都市 $ Y_i $ を $ B_i $ 日目に出発し、王都に $ B_i\ +\ T_{Y_i} $ 日目に到着します。 出発日と到着日を含めて、同じ日に複数の依頼を受けることはできません。また、依頼を受けずに都市間の移動はしません。 報酬はどの依頼を受けても金貨 $ 1 $ 枚です。これらの依頼の中から、最も多くの報酬が得られるように受ける依頼を選んだとき、得られる金貨の枚数を求めてください。 ただし、Treeone 君は最初王都にいて、選んだ全ての依頼を受け終わったときにはどの都市にいても構いません。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ L $ $ T_1 $ $ T_2 $ $ ... $ $ T_N $ $ X_1 $ $ A_1 $ $ X_2 $ $ A_2 $ $ : $ $ X_M $ $ A_M $ $ Y_1 $ $ B_1 $ $ Y_2 $ $ B_2 $ $ : $ $ Y_L $ $ B_L $

答えを $ 1 $ 行に出力してください。

### 制約 - $ 1\ \leq\ N,\ M,\ L\ \leq\ 10^5 $ - $ 0\ \leq\ T_i\ \leq\ 10^9 $ - $ 1\ \leq\ X_i\ \leq\ N $ - $ 1\ \leq\ A_i\ \leq\ 10^9 $ - $ 1\ \leq\ Y_i\ \leq\ N $ - $ 1\ \leq\ B_i\ \leq\ 10^9 $ - 同一の依頼が複数回与えられることはない - 入力は全て整数 ### 部分点 - $ N\ =\ 1 $ を満たすデータセットに正解した場合、$ 30 $ 点が与えられる。 ### Sample Explanation 1 次のように依頼を受けることで $ 3 $ 枚の金貨を得ることができます。 - $ 2 $ 日目 に王都を出発し、$ 3 $ 日目に都市 $ 2 $ に到着する。 - $ 4 $ 日目 に都市 $ 2 $ を出発し、$ 5 $ 日目に王都に到着する。 - $ 6 $ 日目 に王都を出発し、$ 9 $ 日目に都市 $ 1 $ に到着する。 ### Sample Explanation 2 この入力例は部分点の制約を満たしています。 出発日と到着日を含めて、同じ日に複数の依頼を受けることはできないことに注意してください。