← 返回题目列表

AtCoder · awc0056_a

A. 菜谱中的菜品

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

分数: 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