配点 : 500 点
問題文
转生到异世界的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最初是在首都,当你完成所有选定的请求后,你可以在任何城市。
制約
- 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 点。 如果您正确回答了所有满足
入力
输入是按以下格式从标准输入给出的。
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
2 3 2 3 1 1 1 2 2 1 6 1 5 2 4
出力例 1
3
通过接收如下请求: 您可以获得 3 金币。
- 2 第一天从王都出发,3 日城市 移至 2 。 转帐至
- 4 城市日 2 出发5 当天抵达王都。
- 6 第一天从王都出发,9 日城市 移至 1 。 转帐至
入力例 2
1 2 2 0 1 1 1 2 1 1 1 3
出力例 2
2
该输入示例满足部分点约束。
请注意,我们无法在同一天接受多个请求,包括出发和抵达日期。 我有一个带有