题目描述

一天，神犇和 CFF 在玩扑克牌，他们玩的是一种叫做“接竹竿”的游戏。

游戏规则是：一共有 $n$ 张牌，每张牌上有一个花色 $c_i$ 和一个点数 $v_i$，花色不超过 $k$ 种。将这些牌按照给定的顺序依次放入一列牌的末端。若放入之前这列牌中已有与这张牌花色相同的牌，你可以选择将这张牌和任意一张花色相同的牌之间的所有牌全部取出（包括这两张牌本身），并得到与取出的所有牌的点数和相同的分数。取出的牌会从队列中消失，其后面的牌会向前靠拢。

现在已知 CFF 把这 $n$ 张牌放入队列的顺序，请你求出她最多能得多少分。

输入格式

第一行两个整数 $n, k$，分别表示牌的数量和花色的种类数。

第二行 $n$ 个整数 $c_1, c_2, \dots, c_n$，表示依次放入的牌的花色，满足 $1 \le c_i \le k$。

第三行 $n$ 个整数 $v_1, v_2, \dots, v_n$，表示依次放入的牌的点数，满足 $1 \le v_i \le 10^9$。

输出格式

一行一个整数，表示最多能得到的分数。

样例

7 3
1 2 1 2 3 2 3
1 1 1 1 1 1 1

6

样例解释：

初始队列为空，依次处理：

• 第 1 步：加入花色 $1$（点数 $1$），队列：1
• 第 2 步：加入花色 $2$（点数 $1$），队列：1 2
• 第 3 步：加入花色 $1$（点数 $1$），队列：1 2 1
• 第 4 步：加入花色 $2$（点数 $1$）。此时队列中有两个花色 $2$（位置为第 2 和第 4）。选择将第 2 张和第 4 张之间的牌全部取出，即取出 2 1 2（点数 $1+1+1=3$），得到 $3$ 分。队列变为：1
• 第 5 步：加入花色 $3$（点数 $1$），队列：1 3
• 第 6 步：加入花色 $2$（点数 $1$），队列：1 3 2
• 第 7 步：加入花色 $3$（点数 $1$）。此时队列中有两个花色 $3$（位置为第 5 和第 7）。取出 3 2 3（点数 $1+1+1=3$），再得 $3$ 分。队列变为：1

总得分 $3+3=6$。可以证明这是最优方案。

数据范围

• $1 \le n \le 10^6$
• $1 \le k \le 10^6$
• $1 \le v_i \le 10^9$

来源

CodesOnline