分数: 233 分
问题陈述
高桥要参加烹饪比赛。
本次大赛中有 N 主办方准备的基本菜谱类型,每个菜谱都有一个整数值,称为“基本分数”。的基础分数 i-th (1 \leq i \leq N) 基本配方是 A_i.
高桥计划制作 M 菜品。对于 j-th (1 \leq j \leq M) 菜,他会使用基本食谱 B_j 为基础。请注意,不同的菜肴可能使用相同的基本食谱作为其底料。
每道菜的分数是底层基础菜谱的基础分数加上排列分数 高桥补充道 S_j 。也就是说,分数 j第道菜是 A_{B_j} + S_j。排列得分可以为负数,在这种情况下,菜肴的得分将低于基本得分。菜肴本身的分数也有可能是负数。
比赛中,高桥的排名由选手的总成绩决定 M 他做的菜。
求高桥菜肴的总分。请注意,总分可能为负数。
约束
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq B_j \leq N (1 \leq j \leq M)
- -10^9 \leq S_j \leq 10^9 (1 \leq j \leq M)
- 所有输入值均为整数
输入
N M A_1 A_2 \ldots A_N B_1 S_1 B_2 S_2 \vdots B_M S_M
- 第一行包含基本菜谱数量 N 和高桥制作的菜肴数量 M,用空格分隔。
- 第二行包含 N 整数 A_1, A_2, \ldots, A_N 代表每个基本配方的基本分数,以空格分隔。
- 以下 M 行提供有关高桥制作的每道菜的信息。
- 的 (2 + j)第行 (1 \leq j \leq M) 包含号码 用作基础的基本配方的 B_j 用作基础的基本配方 j第道菜和排列分数 S_j 添加到该盘中,以空格分隔。
输出
输出总分 M 高桥制作的菜肴,在一行上。
示例输入 1
3 2 10 20 30 1 5 3 -10
示例输出 1
35
示例输入 2
5 4 100 200 300 400 500 2 50 4 -100 1 200 5 0
示例输出 2
1350
示例输入 3
10 8 1000000000 500000000 300000000 700000000 100000000 900000000 200000000 800000000 600000000 400000000 1 -500000000 6 1000000000 3 -300000000 10 999999999 5 100000000 8 -800000000 2 500000000 7 0
示例输出 3
5199999999