#P50080. 「LibreOJ NOI Round #1」接竹竿

「LibreOJ NOI Round #1」接竹竿

题目描述

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

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

输入顺序即为 LCR 放入队列的顺序。即,cic_i 表示第 ii 张放入的牌的花色,viv_i 表示第 ii 张放入的牌的点数。

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

输入格式

第一行两个整数 n,kn,k
第二行,nn 个整数 c1,c2,...,cnc_1,c_2,...,c_n 表示花色,满足 1cik1\leq c_i\leq k
第三行,nn 个整数 v1,v2,...,vnv_1,v_2,...,v_n 表示点数。

输出格式

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

样例 1

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

第 1 步,向队列加入 11。现在的队列:11 第 2 步,向队列加入 22。现在的队列:1,21,2 第 3 步,向队列加入 11。现在的队列:1,2,11,2,1 第 4 步,向队列加入 22,取出 2,1,22,1,2。现在的队列:11 第 5 步,向队列加入 33。现在的队列:1,31,3 第 6 步,向队列加入 22。现在的队列:1,3,21,3,2 第 7 步,向队列加入 33,取出 3,2,33,2,3。现在的队列:11

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

见附加文件或备用网盘链接(提取码:a795

数据范围与提示

对于 100%100\% 的数据,1n106,1k106,1vi1091\leq n\leq 10^6,1\leq k\leq 10^6,1\leq v_i\leq 10^9

Subtask # 分值 n,kn,k 的限制 特殊限制
1 1515 1n,k151\leq n,k\leq 15 ci=vic_i=v_i
2 1n,k3001\leq n,k\leq 300
3 3030 1n,k30001\leq n,k\leq 3000
4 1515 1n,k2×1051\leq n,k\leq 2\times 10^5
5 1010 1n,k1061\leq n,k\leq 10^6 ci=vic_i=v_i
6 1515