题目描述

有 $N$ 头奶牛（$3$ <= $N$ <= $100$）在田地中间吃草。为了防止它们走丢，农夫约翰想把它们连成一个圈，即奶牛 $i$ 与奶牛 $i-1$ 和 $i+1$ 相连（奶牛 $N$ 与奶牛 $1$ 相连以完成这个圈）。

每头奶牛都有一些它喜欢的吃草地点，并且只有当它位于其中一个喜欢的地点时才会开心。假设农夫约翰在安置奶牛时必须保证它们开心，计算他将所有奶牛连成圈所需的最短绳子长度。圈的不同部分可能会相互交叉。

输入

• 第一行：整数 $N$。
• 第 $2$ 行到第 $N+1$ 行：每行描述一头奶牛，使用几个空格分隔的整数。第一个整数是这头奶牛喜欢的地点数量 $S$（$1$ <= $S$ <= $40$）。接下来是 $2*S$ 个整数，表示这些地点的 $(x, y)$ 坐标。坐标范围是 $-100$ 到 $100$。

输出

一行，包含一个整数，表示所需的最短绳子长度的 $100$ 倍（对于这个结果不需要进行特殊的四舍五入）。

示例输入

4
1 0 0
2 1 0 2 0
3 -1 -1 1 1 2 2
2 0 1 0 2

示例输出

400

提示

[奶牛 1 位于 $(0,0)$；奶牛 2 位于 $(1,0)$；奶牛 3 位于 $(1,1)$；奶牛 4 位于 $(0,1)$。]

来源

USACO 2003 年 2 月 Orange 组