A - Reception Processing at the Service Window Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君は市役所の総合案内係として働いています。この市役所では、年度末になると手続きの申請が殺到するため、効率的な窓口管理が求められています。

市役所には N 個の窓口があり、窓口には 1 から N までの番号が付いています。各窓口 i (1 \leq i \leq N) には1日の受付上限 C_i が定められており、その日に最大 C_i 件までの申請を受け付けることができます。1日の始まりの時点では、すべての窓口の受付済み件数は 0 です。

ある日、M 件の申請が順番に届きました。j 番目 (1 \leq j \leq M) の申請では、市民が窓口 T_j での手続きを希望しています。

申請は j = 1, 2, \ldots, M の順に1件ずつ処理されます。各申請 j について、以下のように処理が行われます。

  • 希望する窓口 T_j の、その時点での受付済み件数が受付上限 C_{T_j} 未満であれば、その申請は受理され、窓口 T_j の受付済み件数が 1 増えます。
  • 希望する窓口 T_j の、その時点での受付済み件数が受付上限 C_{T_j} に等しい（すなわち受付上限に達している）場合、その申請は却下されます。却下された場合、受付済み件数は変化せず、他の窓口に振り替えられることもありません。

すべての申請を処理した後、受理された申請の総件数を求めてください。

制約

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

入力

N M
C_1 C_2 \ldots C_N
T_1
T_2
\vdots
T_M
  • 1 行目には、窓口の数を表す整数 N と、申請の件数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、各窓口の1日の受付上限を表す整数 C_1, C_2, \ldots, C_N が、スペース区切りで与えられる。
  • 3 行目から 2 + M 行目までの各行には、申請で希望される窓口の番号が1つずつ与えられる。このうち (2 + j) 行目 (1 \leq j \leq M) には、j 番目の申請で希望される窓口の番号 T_j が与えられる。

出力

受理された申請の総件数を1行で出力してください。

入力例 1

3 5
2 1 3
1
2
1
1
2

出力例 1

3

入力例 2

4 10
3 2 1 4
1
2
3
4
1
2
3
1
4
4

出力例 2

9

入力例 3

5 15
1000000000 1 2 3 1
1
1
1
2
2
3
3
3
4
4
4
4
5
5
1

出力例 3

11

Score : 233 pts

Problem Statement

Takahashi works as a general information clerk at a city hall. At this city hall, applications for procedures flood in at the end of the fiscal year, so efficient counter management is required.

The city hall has N counters, numbered from 1 to N. Each counter i (1 \leq i \leq N) has a daily reception limit C_i, meaning it can accept up to C_i applications per day. At the beginning of the day, the number of accepted applications at every counter is 0.

On a certain day, M applications arrived in order. The j-th application (1 \leq j \leq M) is from a citizen who wishes to have their procedure handled at counter T_j.

The applications are processed one by one in the order j = 1, 2, \ldots, M. Each application j is processed as follows:

  • If the current number of accepted applications at the desired counter T_j is less than the reception limit C_{T_j}, the application is accepted, and the number of accepted applications at counter T_j increases by 1.
  • If the current number of accepted applications at the desired counter T_j is equal to the reception limit C_{T_j} (i.e., the reception limit has been reached), the application is rejected. In the case of rejection, the number of accepted applications does not change, and the application is not redirected to any other counter.

After processing all applications, find the total number of accepted applications.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq T_j \leq N (1 \leq j \leq M)
  • All input values are integers

Input

N M
C_1 C_2 \ldots C_N
T_1
T_2
\vdots
T_M
  • The first line contains two integers separated by a space: N, the number of counters, and M, the number of applications.
  • The second line contains N integers separated by spaces: C_1, C_2, \ldots, C_N, representing the daily reception limit of each counter.
  • From the 3rd line to the (2 + M)-th line, each line contains the counter number desired in an application. Specifically, the (2 + j)-th line (1 \leq j \leq M) contains T_j, the counter number desired in the j-th application.

Output

Print the total number of accepted applications in a single line.

Sample Input 1

3 5
2 1 3
1
2
1
1
2

Sample Output 1

3

Sample Input 2

4 10
3 2 1 4
1
2
3
4
1
2
3
1
4
4

Sample Output 2

9

Sample Input 3

5 15
1000000000 1 2 3 1
1
1
1
2
2
3
3
3
4
4
4
4
5
5
1

Sample Output 3

11