Cowties

Interview

Time limit1sMemory limit1024 MB

Summary

Pick one preferred spot per cow so that the closed loop of rope through all cows has the minimum total Euclidean length.

Level: Medium5 of 10
Topics: Dynamic programming, Geometry
Solved: No attempts yet

Problem

N cows (3 ≤ N ≤ 100) are grazing in the middle of a field. To keep them from getting lost, Farmer John ties them together in a loop, so that cow i is attached to cows i-1 and i+1. Cow N is tied to cow 1 to close the loop.

Each cow is happy only when she stands at one of her preferred grazing spots. Farmer John must keep every cow happy when he places them. Find the shortest length of rope needed to tie all cows in a loop. Different parts of the loop may cross each other.

Input

The first line contains the integer N. Each of the next N lines describes one cow. The first integer on the line is the number of preferred spots S (1 ≤ S ≤ 40), followed by 2S integers that give the $(x,y)$ coordinates of those spots. Every coordinate lies in the range -100 to 100.

Output

Print one integer: 100 times the minimum length of rope needed. Do not round this result.

Examples1

Example 1

Input

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

Expected output