Background

Description

上学的时候经常换同桌，有时我们会用同桌关系来描述两个人，如小 Y 的前同桌的同桌是他的好朋友小 C,同样的我们可以用这样的关系描述班上几乎所有人（有些受到特殊关照的人除外）。

一般我们会用最短的同桌描述，比如一个人是我同桌的前同桌（7个字），也是我的前同桌的前前前同桌的同桌（14个字），显然我们会使用前者，我们把汉字字数定义成亲密度（显然是越小越好），如果关系无法描述，则亲密度为无限。
现在老师要再次排座位，为了让同学们更加亲密，需要满足在新座位后，同学们两两之间亲密度之和最小

Format

Input

第一行两个数 \(k\) ，\(n\) 表示之前有几轮座位，班上有几个人。
接下来 \(k\) 轮，每轮 \(n/2\) 行，每行两个数，表示哪两个人是同桌。（第一轮年代最久远，第 \(k\) 轮最靠近现在。）

Output

最小亲密度之和

Sample 1

Input1

2 4
1 2
3 4
1 3
2 4

Output1

30

Input 2

1 6
1 2
3 4
5 6

Output 2

108

Limination

对于 \(\% 40 % \) 的数据

\( n,k\le 8\)

对于 \(\% 100% \) 的数据

\( n,k \le 14\)

Hint

座位安排为

1 4
2 3

1-2, 3-4 : 我的前前同桌
1-3, 2-4 : 我的前同桌
1-4, 2-3 : 我的同桌
所有人对对方的亲密度都是 4 (我的同桌）