← 返回题目列表

Codeforces · 802/A3

A3. 海蒂和图书馆(硬)

中文机器翻译题面 查看原题

海蒂图书馆的美好时光结束了。土拨鼠终于有了互联网连接,完全不再来图书馆了。不仅如此,书店还开始对一些书籍收取高价。也就是说,在以前的版本中,每本书可以 1 瑞士法郎购买,而现在一本书的价格 i is ci 瑞士法郎。

输入

输入的第一行将包含两个整数 n 和 k ()。第二行将包含 n 整数 a1, a2, ..., an (1 ≤ ai ≤ n) – 图书请求的顺序。第三行包含 n 整数 c1, c2, ..., cn (0 ≤ ci ≤ 106) – 书籍的成本。

输出

在一行中打印在商店购买书籍的最低费用,以满足所有要求。

示例

输入
复制

4 80
1 2 2 1
1 1 1 1

输出
复制

2

输入
复制

4 1
1 2 2 1
1 1 1 1

输出
复制

3

输入
复制

4 2
1 2 3 1
1 1 1 1

输出
复制

3

输入
复制

7 2
1 2 3 1 1 1 2
1 10 1 0 0 0 0

输出
复制

13

注意

前三个示例案例是重复的,但第四个示例案例是新的。

在第四个测试用例中,购买书籍时 3,海蒂应该丢弃其中一本书 1 or 2。尽管书 2 的请求将晚于预订 1,她应该保留它,因为再次购买太贵了。