Description:


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

游戏规则是:一共有 \(n\) 张牌,每张牌上有一个花色 \(c\) 和一个点数 \(v\) ,花色不超过 \(k\) 种。将这些牌依次放入一列牌的末端。若放入之前这列牌中已有与这张牌花色相同的牌,你可以选择将这张牌和任意一张花色相同的牌之间的所有牌全部取出队列(包括这两张牌本身),并得到与取出的所有牌点数和相同的分数。现在已知 LCR 把这 \(n\) 张牌放入队列的顺序,求她最多能得多少分。

输入顺序即为 LCR 放入队列的顺序。即, \(c_i\) 表示第 \(i\) 张放入的牌的花色, \(v_i\) 表示第 \(i\) 张放入的牌的点数。

请注意,如果你知道类似的纸牌游戏,请尤其仔细地阅读规则,以免因为理解题意错误而出现不必要的问题。

Input:


第一行两个整数 \(n,k\)
第二行, \(n\) 个整数 \(c_1,c_2,\ldots ,c_n\) 表示花色,满足 \(1\le c_i\le k\)
第三行, \(n\) 个整数 \(v_1,v_2,\ldots ,v_n\) 表示点数。

Output:


输出一行一个整数,表示最多能得到的分数。

Sample Input:


Sample Output:


题解:


突然想做一下LOJ的题目。

可以发现就是原序列中选几段,每一段开头结尾颜色相同。

\(dp_i\) 为1~i的答案。
可以显然地发现dp式子(sum表示v的前缀和):

然后就是 \(O(n)\) 了。