← 返回题目列表

AtCoder · code_thanks_festival_2018_g

G. 卡牌总和

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

配点 : 500 点

問題文

高桥先生,开头 在 N 卡的正面 1 我决定将所有值添加到 N 整数 1 一张一张写完后,翻过来,打乱顺序,然后 1 我决定将所有值添加到 N 整数 1 我一一写的。

1 \leq i \leq N 第二张牌有 a_i 位于背面 写入b_i 。

这个 我将 N 卡放在他们最喜欢的一面朝上,并尝试最大化可见整数的总和。

然而,事实上,这对高桥君来说太容易了。

高桥先生很伤心,因为他能看到的整数类型太少了,所以K 我决定在可以看到不止一种类型的整数的情况下找到总和的最大值。

请为高桥君计算这个值。

制約

  • 1 \leq K \leq N \leq 5000
  • 1 \leq a_i, b_i \leq N
  • a_1, a_2, ..., a_N 有 1, 2, ..., N 是 在 1 以度为单位显示。
  • b_1, b_2, ..., b_N 有 1, 2, ..., N 是 在 1 以度为单位显示。
  • 所有输入均为整数

入力

输入将以以下形式从标准输入给出。

N K
a_1 a_2 ... a_{N-1} a_N
b_1 b_2 ... b_{N-1} b_N

出力

打印总和的最大值。


入力例 1

2 2
2 1
1 2

出力例 1

3

双方都是 \{1, 2\} 卡和 有一张 \{2, 1\} 的卡片。

将两面朝上或两面朝下。 2 您可以使整数可见,总和为 3 。


入力例 2

2 1
2 1
1 2

出力例 2

4

双方都是 \{1, 2\} 卡和 有一张 \{2, 1\} 的卡片。

两者 您可以将 2 的一面朝上,则总和为 4 是最大值。


入力例 3

3 2
2 3 1
1 3 2

出力例 3

7