配点 : 100 点
問題文
长度为 n 序列 a 和一个正整数 对于 k ,当满足以下条件时, a 在 k- 定义为连续的数字序列。
- 全部 对于 i\ (1 \le i \le n) ,一些正整数对 (l,r) 存在并且 l\le i < r 和 k \le r-l 和 a_l=a_{l+1}=\ldots=a_{r-1} 成立。
例如, a=(1,1,1,2,2,2,2,3,3,3) 是 给出了 3- 连续。特别是, a=() 则任意正整数 t 反对 t- 请注意它是连续的。
正整数 N,K 和长度 给出了 N 的正整数序列 C,W 。您可以执行以下操作 您可以在 0 内执行此操作任意多次。 选择
- 整数 i 。成本 支付 W_i , C_i,W_i 分别 从 C,W 中删除。
C 在 K- 求使其连续所需的最小成本总和。
制約
- 1 \leq K \leq N \leq 2\times 10^5
- 1 \leq C_i \leq N
- 1 \leq W_i \leq 10^9
- 所有输入均为整数
部分点
- N \leq 300 的数据集,10 奖励积分。 如果正确答案是满足
- N \leq 3000 的数据集,除了上述之外, 10 奖励积分。 如果正确答案是满足
- 如果对于没有附加约束的数据集,除了上述之外,答案是正确的, 80 奖励积分。 如果正确答案是满足
入力
输入是按以下格式从标准输入给出的。
N K C_1 C_2 \ldots C_N W_1 W_2 \ldots W_N
出力
打印答案。 元素小于
入力例 1
4 2 1 1 2 1 1 2 3 4
出力例 1
3
入力例 2
2 1 1 2 10 10
出力例 2
0
入力例 3
10 2 3 1 4 1 5 9 2 6 5 3 58 97 93 23 84 62 64 33 83 27
出力例 3
337