VU atrankinis turas 2005 m. ACM ICPC varžyboms

N people (2 ≤ N < 25) were registered for participation in a rope-pulling competition. The participants are numbered from 1 to N. There are M pairs of participants (0 ≤ M ≤ N*(N-1)/2) who know each other. The relation is not transitive (if A and B both know C, it does not necessarily mean that they also know each other).

The organizers of the competition need to divide all participants into two teams so that the teams would consist of K and (N-K) contestants respectively (1 ≤ K < N). In organizers’ opinion, the most important attribute of a team is its unity — the number of pairs of participants who know each other in the team. The organizers want to divide all participants into two teams so that the total of unities of both teams would be as big as possible.

Input

The first line of the input contains three numbers N, K, and M, separated by spaces. Each of the following M lines contains two numbers P_i and Q_i (1 ≤ P_i,Q_i ≤ N, P_i ≠ Q_i, 1 ≤ i ≤ M). These numbers encode a pair of participants who know each other.

Output

The first and only line of the output file should contain a single integer T — the maximal possible total unity.

Sample Input

5 3 3
1 3
2 5
5 4

Sample Output

3

The way to achieve the total unity 3 is to have the participants 1 and 3 in one team (team unity 1) and the participants 2, 4, and 5 in the other (team unity 2).