問題文

高橋君は、初めに 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 度ずつ現れる。
• 入力は全て整数である

入力例 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