海蒂图书馆的美好时光结束了。土拨鼠终于有了互联网连接,完全不再来图书馆了。不仅如此,书店还开始对一些书籍收取高价。也就是说,在以前的版本中,每本书可以 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,她应该保留它,因为再次购买太贵了。