← 返回题目列表

AtCoder · qupc2018_d

D. 小说家

中文机器翻译题面 查看原题

配点 : 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

该输入示例满足部分点约束。

请注意,我们无法在同一天接受多个请求,包括出发和抵达日期。 我有一个带有