問題文

作家の太郎君は、N ページの小説を執筆しました。この小説には M 個の繋がりがあり、i 個目の繋がりは A_i ページ目と B_i ページ目です。

いま、彼は小説を K 個の章に分割しようとしています。同じ章に存在する繋がりの個数を「小説の良さ」とするとき、小説の良さの最大値はいくつですか。

制約

• 入力はすべて整数
• 2 \leqq N \leqq 288
• 1 \leqq M \leqq 50
• 1 \leqq K \leqq 10
• K \leqq N
• 1 \leqq A_i < B_i \leqq N (1 \leqq i \leqq M)

入力例 1

6 4 3
3 4
3 5
2 5
1 6

出力例 1

3

入力例 2

4 6 1
1 2
1 3
1 4
2 3
2 4
3 4

出力例 2

6

入力例 3

10 4 10
1 3
2 4
2 3
1 4

出力例 3

0