Assign Values

Assign the values 1..N to the N vertices, using each value exactly once. Find the maximum total, over all edges, of the sum of the values at the two endpoints. The original site's example edge arrays had inconsistent lengths, so this site rewrote the input from the four edges described in the text.

输入格式

This site's input: the first line contains N M (1≤N≤100000, 0≤M≤200000), followed by M lines, each an undirected edge u v, with vertices numbered 1..N; the graph is guaranteed to be simple.

输出格式

Output a single integer, the answer.

样例 1

输入：

5 4
2 3
2 1
1 4
2 4

输出：

31

样例 2

输入：

1 0

输出：

0

样例 3

输入：

3 2
1 2
2 3

输出：

9

样例说明

Example 1: the degrees sorted are 0, 1, 2, 2, 3; multiplying them by 1, 2, 3, 4, 5 respectively gives a total of 31.

Example 2: there are no edges, so every assignment gives a total of 0.

Example 3: assign 3 to the center and 1, 2 to the ends; the edge sums are 4+5=9.