소설가 타로 군은 $N$ 페이지 분량의 소설을 집필했습니다. 이 소설에는 총 $M$ 개의 사건 간 연결 고리가 있으며, $i$ 번째 연결 고리는 $A_i$ 페이지와 $B_i$ 페이지를 잇습니다.
타로 군은 이 소설을 연속한 페이지들로 구성된 $K$ 개의 장(Chapter)으로 분할하려 합니다. 각 장은 $1$ 페이지 이상이어야 하며, $1$ 페이지부터 $N$ 페이지까지 순서대로 빠짐없이 포함되어야 합니다.
두 페이지가 같은 장에 속해 있을 때만 그 연결 고리가 독자에게 온전히 전달된다고 합니다. 같은 장 내에 양 끝 페이지가 모두 포함되는 연결 고리의 개수를 "소설의 완성도"라고 할 때, 얻을 수 있는 완성도의 최댓값을 구하는 프로그램을 작성하십시오.

[제약 조건]
• $1 \le N \le 200$
• $1 \le M \le 2{,}000$
• $1 \le K \le \min(N, 10)$
• $1 \le A_i < B_i \le N$
• $i \neq j$ 이면 $(A_i, B_i) \neq (A_j, B_j)$ 입니다.
• 입력되는 모든 값은 정수입니다.

첫째 줄에 세 정수 $N, M, K$ 가 공백으로 구분되어 주어집니다.
둘째 줄부터 $M$ 개의 줄에 걸쳐 각 연결 고리가 잇는 두 페이지 번호 $A_i, B_i$ 가 공백으로 구분되어 주어집니다.

소설 완성도의 최댓값을 출력하십시오.

6 4 3
3 4
3 5
2 5
1 6

3