← 返回题目列表

AtCoder · pakencamp_2024_day3_1_b

B. 彩色瓶子

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

配点 : 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