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

内存限制:512 MiB 时间限制:600 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: liu_cheng_ao

题目描述

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

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

输入顺序即为 LCR 放入队列的顺序。即,cic_ici 表示第 iii 张放入的牌的花色,viv_ivi 表示第 iii 张放入的牌的点数。

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

输入格式

第一行两个整数 n,kn,kn,k
第二行,nnn 个整数 c1,c2,...,cnc_1,c_2,...,c_nc1,c2,...,cn 表示花色,满足 1≤ci≤k1\leq c_i\leq k1cik
第三行,nnn 个整数 v1,v2,...,vnv_1,v_2,...,v_nv1,v2,...,vn 表示点数。

输出格式

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

样例

样例输入 1

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

样例输出 1

13

样例解释 1

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

样例输入 2

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

样例输出 2

123

更多样例

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

数据范围与提示

对于 100%100\%100% 的数据,1≤n≤106,1≤k≤106,1≤vi≤1091\leq n\leq 10^6,1\leq k\leq 10^6,1\leq v_i\leq 10^91n106,1k106,1vi109

Subtask # 分值 n,kn,kn,k 的限制 特殊限制
1 151515 1≤n,k≤151\leq n,k\leq 151n,k15 ci=vic_i=v_ici=vi
2 151515 1≤n,k≤3001\leq n,k\leq 3001n,k300 ci=vic_i=v_ici=vi
3 303030 1≤n,k≤30001\leq n,k\leq 30001n,k3000
4 151515 1≤n,k≤2×1051\leq n,k\leq 2\times 10^51n,k2×105
5 101010 1≤n,k≤1061\leq n,k\leq 10^61n,k106 ci=vic_i=v_ici=vi
6 151515 1≤n,k≤1061\leq n,k\leq 10^61n,k106