A - Concert Ticket Reservation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は、人気アーティストのコンサートチケット予約システムを管理しています。

このコンサート会場には N 種類の座席エリアがあり、それぞれ 1 から N までの番号が付けられています。各エリア i (1 \leq i \leq N) には、チケット価格 C_i と、そのエリアの定員（座席数） K_i が設定されています。

M 人のファンが 1 番目から M 番目まで順番に、それぞれ 1 回ずつチケットの予約を試みます。j 番目のファンはエリア P_j のチケットを予約しようとします。その時点でエリア P_j の予約済み人数が定員 K_{P_j} 未満であれば、そのファンはエリア P_j のチケットを予約でき、エリア P_j の予約済み人数が 1 増えます。すでに予約済み人数が定員 K_{P_j} に等しい場合、そのファンは予約できません。予約できなかったファンが他のエリアに振り替えて予約することはありません。

すべてのファンの予約処理が終わった後、実際にチケットの予約が成立したファンのチケット価格の合計を求めてください。エリア i のチケットを予約したファンのチケット価格は C_i です。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq C_i \leq 10^4 (1 \leq i \leq N)
  • 1 \leq K_i \leq 10^5 (1 \leq i \leq N)
  • 1 \leq P_j \leq N (1 \leq j \leq M)
  • 入力はすべて整数である

入力

N M
C_1 K_1
C_2 K_2
\vdots
C_N K_N
P_1
P_2
\vdots
P_M
  • 1 行目には、座席エリアの数 N と、ファンの数 M が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目には、エリア i のチケット価格 C_i と定員 K_i が、スペース区切りで与えられる。
  • 続く M 行のうち j 行目には、j 番目のファンが予約しようとするエリアの番号 P_j が与えられる。

出力

実際にチケットの予約が成立したファンのチケット価格の合計を 1 行で出力せよ。

入力例 1

2 5
500 2
1000 1
1
1
1
2
2

出力例 1

2000

入力例 2

3 8
300 3
700 2
1500 1
1
2
3
1
2
1
3
2

出力例 2

3800

入力例 3

5 12
1000 2
2500 3
800 1
5000 2
1200 4
1
2
3
4
5
1
2
2
3
4
5
5

出力例 3

23900

Score : 266 pts

Problem Statement

Takahashi is managing a reservation system for concert tickets of a popular artist.

The concert venue has N types of seating areas, numbered from 1 to N. Each area i (1 \leq i \leq N) has a ticket price C_i and a capacity (number of seats) K_i.

M fans, from the 1-st to the M-th, attempt to reserve tickets one at a time in order. The j-th fan tries to reserve a ticket for area P_j. If the number of reservations already made for area P_j at that point is less than the capacity K_{P_j}, the fan successfully reserves a ticket for area P_j, and the number of reservations for area P_j increases by 1. If the number of reservations already equals the capacity K_{P_j}, the fan cannot make a reservation. A fan who fails to reserve does not attempt to reserve in any other area.

After all fans have been processed, find the total ticket price of the fans who successfully reserved tickets. The ticket price for a fan who reserved a ticket in area i is C_i.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq C_i \leq 10^4 (1 \leq i \leq N)
  • 1 \leq K_i \leq 10^5 (1 \leq i \leq N)
  • 1 \leq P_j \leq N (1 \leq j \leq M)
  • All input values are integers

Input

N M
C_1 K_1
C_2 K_2
\vdots
C_N K_N
P_1
P_2
\vdots
P_M
  • The first line contains the number of seating areas N and the number of fans M, separated by a space.
  • The following N lines each contain, for the i-th line, the ticket price C_i and capacity K_i of area i, separated by a space.
  • The following M lines each contain, for the j-th line, the area number P_j that the j-th fan tries to reserve.

Output

Print the total ticket price of the fans who successfully reserved tickets, on a single line.

Sample Input 1

2 5
500 2
1000 1
1
1
1
2
2

Sample Output 1

2000

Sample Input 2

3 8
300 3
700 2
1500 1
1
2
3
1
2
1
3
2

Sample Output 2

3800

Sample Input 3

5 12
1000 2
2500 3
800 1
5000 2
1200 4
1
2
3
4
5
1
2
2
3
4
5
5

Sample Output 3

23900