G - Sum of Cards

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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, ..., N1 度ずつ現れる。
  • b_1, b_2, ..., b_N には 1, 2, ..., N1 度ずつ現れる。
  • 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

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