/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 233 点
問題文
高橋君は料理コンテストに参加することになりました。
このコンテストでは、主催者が用意した N 種類の基本レシピがあり、それぞれのレシピには「基本点」と呼ばれる整数値が設定されています。i 番目 (1 \leq i \leq N) の基本レシピの基本点は A_i です。
高橋君は M 品の料理を作る予定です。j 番目 (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
- 1 行目には、基本レシピの数 N と、高橋君が作る料理の数 M がスペース区切りで与えられる。
- 2 行目には、各基本レシピの基本点を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。
- 続く M 行にわたって、高橋君が作る各料理の情報が与えられる。
- 2 + j 行目 (1 \leq j \leq M) には、j 番目の料理でベースにする基本レシピの番号 B_j と、その料理に加えるアレンジ点 S_j がスペース区切りで与えられる。
出力
高橋君が作った M 品の料理の得点の合計値を 1 行で出力せよ。
入力例 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
Score : 233 pts
Problem Statement
Takahashi is going to participate in a cooking contest.
In this contest, there are N types of basic recipes prepared by the organizers, each of which has an integer value called a "base score." The base score of the i-th (1 \leq i \leq N) basic recipe is A_i.
Takahashi plans to make M dishes. For the j-th (1 \leq j \leq M) dish, he will use basic recipe B_j as the base. Note that different dishes may use the same basic recipe as their base.
The score of each dish is the base score of the underlying basic recipe plus the arrangement score S_j that Takahashi adds. That is, the score of the j-th dish is A_{B_j} + S_j. The arrangement score can be negative, in which case the dish's score will be lower than the base score. It is also possible for the dish's score itself to be negative.
In the contest, Takahashi's ranking is determined by the total score of the M dishes he makes.
Find the total score of Takahashi's dishes. Note that the total score may be negative.
Constraints
- 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)
- All input values are integers
Input
N M A_1 A_2 \ldots A_N B_1 S_1 B_2 S_2 \vdots B_M S_M
- The first line contains the number of basic recipes N and the number of dishes Takahashi makes M, separated by a space.
- The second line contains N integers A_1, A_2, \ldots, A_N representing the base scores of each basic recipe, separated by spaces.
- The following M lines provide information about each dish Takahashi makes.
- The (2 + j)-th line (1 \leq j \leq M) contains the number B_j of the basic recipe used as the base for the j-th dish and the arrangement score S_j added to that dish, separated by a space.
Output
Output the total score of the M dishes Takahashi made, on a single line.
Sample Input 1
3 2 10 20 30 1 5 3 -10
Sample Output 1
35
Sample Input 2
5 4 100 200 300 400 500 2 50 4 -100 1 200 5 0
Sample Output 2
1350
Sample Input 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
Sample Output 3
5199999999