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