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