Heidi and Library (hard)
题号:NC245486
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

你有一个容量为 k 的空书架,现在共有 n 个请求,每个请求给定一本书 a_i,如果你的书架里没有这本书,你就必须以 的价格购买这本书放入书架。当然,你可以在任何时候丢掉书架里的某本书。请求出完成这 n 个请求所需要的最少价钱。

输入描述:

第一行两个整数nk 
接下来一行n个整数
第三行n个整数

输出描述:

一个整数表示答案。
示例1

输入

复制
4 80
1 2 2 1
1 1 1 1

输出

复制
2
示例2

输入

复制
4 1
1 2 2 1
1 1 1 1

输出

复制
3
示例3

输入

复制
4 2
1 2 3 1
1 1 1 1

输出

复制
3
示例4

输入

复制
7 2
1 2 3 1 1 1 2
1 10 1 0 0 0 0

输出

复制
13