← 返回题目列表

AtCoder · awc0034_a

A. 服务窗口受理处理

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

分数: 233 分

问题陈述

高桥在市政府担任综合信息员。在本市政府,财政年度末,办理手续的申请大量涌入,因此需要高效的柜台管理。

市政府有 N 计数器,编号自 1 to N。各柜台 i (1 \leq i \leq N) 每日接收限额 C_i,这意味着它最多可以接受 C_i 每天申请。当日开始时,各柜台受理申请数量为 0.

在某一天, M 申请按顺序送达。的 j第一个应用程序 (1 \leq j \leq M) 来自一位希望在柜台办理手续的公民 T_j.

申请按顺序一一处理 j = 1, 2, \ldots, M。每个申请 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
  • 第一行包含两个用空格分隔的整数: N,计数器的数量,以及 M,申请数量。
  • 第二行包含 N 由空格分隔的整数: C_1, C_2, \ldots, C_N,代表各柜台每日接待限额。
  • 从第 3 行到 (2 + M)第行,每行包含应用程序中所需的计数器编号。具体来说, (2 + j)第行 (1 \leq j \leq M) 包含 T_j,所需的计数器编号 j第一个应用程序。

输出

在一行中打印已接受的申请总数。


示例输入 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