Description

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

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

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

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

Input Format

第一行两个整数n,k。

第二行，n个整数c_1,c_2,c_3,......,c_n表示花色，满足1≤c_i≤k。

第三行，n个整数v_1,v_2,v_3,......,v_n表示点数。

Output Format

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

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

13

Hint

【样例1解释】

第 1 步，向队列加入1。现在的队列：1；第 2 步，向队列加入2，现在的队列：1，2；第 3 步，向队列加入1。现在的队列：1，2，1；第 4 步，向队列加入2，取出2，1，2，现在的队列：1；第 5 步，向队列加入3，现在的队列：1，3；第 6 步，向队列加入2，现在的队列：1，3，2；第 7 步，向队列加入3，取出3，2，3；现在的队列：1

【数据范围与测试点】

对于100%的数据，1≤n≤10^6，1≤k≤10^6，1≤v_i≤10^9。

Source

CodesOnline