Description

一块草地上有n头绵羊，编号为1到n，每头绵羊都有自己喜欢的地方，也就是除了这些地方，其它地方吃草都没胃口。为了不让这些绵羊走散，你需要找条绳子将它们连接起来，连接方法为1号与2号相连，2号与3号相连，……，n-1号与n号相连，n号与1号相连，同时不能把绵羊安置在它不喜欢的地方。现要你寻找一种安置方法使得绳子总长度最短。

Input

输入包含多组测试数据。 每组数据的第一行为一个整数n，表示绵羊总数。 接下来有n行。每行的以一个整数s开头，表示当前这头绵羊喜欢的地方数，紧跟着s对坐标（x，y），表示每个地方的坐标（ 3<=n<=100,1<=s<=40）。坐标x、y的范围都为[-100,100]。

Output

针对每组测试数据，输出最短的绳子长度*100后的整数部分。

Sample

Input

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

Output

400