← 返回题目列表

Codeforces · 387/E

E. 乔治和卡兹

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

乔治是一只猫,所以他非常喜欢玩。

维塔利将n张牌排成一排放在乔治面前。每张卡片上都写有一个整数。所有卡片上都写有不同的数字。让我们从左到右用 1 到 n 的整数对卡片进行编号。那么左起第 i 张卡包含数字 pi (1 ≤ pi ≤ n)。

Vitaly 希望该行正好剩下 k 张牌。他还希望左起第i张卡片上写有数字bi。 Vitaly 给 George 分配了一项任务,即使用删除操作 n - k 次来获取所需的卡片序列。

在一次删除操作中,George 可以选择 w(1 ≤ w;w 不大于该行中当前卡片的数量)张连续卡片(卡片的连续子段)。我们将这些卡片上写的数字表示为 x1、x2、...、xw(从左到右)。之后,George 可以移除卡片 xi,使得对于每个 j (1 ≤ j ≤ w),xi ≤ xj。在所描述的操作之后,乔治得到了 w 块香肠。

乔治想知道:如果他达到目标并且表现最佳,他总共最多能得到多少根香肠?帮助乔治,找到他问题的答案!

输入

第一行包含整数 n 和 k (1 ≤ k ≤ n ≤ 106) — 初始和最终的牌数。

第二行包含 n 个不同的空格分隔整数 p1, p2, ..., pn (1 ≤ pi ≤ n) — 卡片的初始行。

第三行包含 k 个空格分隔的整数 b1, b2, ..., bk — 您需要获得的卡片行。保证通过n-k次删除操作可以获得给定的行。

输出

打印一个整数——如果乔治表现最佳,他可以获得的最大香肠数。

示例

输入 #1

3 2
2 1 3
1 3

输出 #1

1

输入 #2

10 5
1 2 3 4 5 6 7 8 9 10
2 4 6 8 10

输出 #2

30