403868: GYM101343 J Husam and the Broken Present 2

After you helped Husam and rebuilt his beautiful array a he became very happy. To avoid losing his array again, Husam made n copies from it, and distributed it to n of his friends. After that Husam became sure that he can rebuild the array a again if he lost it, so he destroyed the table t.

Today, Husam was looking for his array a, but he was not able to find it. Husam visited all his n friends to take a copy from the array. Unfortunately, all his friends thought that the length of the array a was very long, so instead of keeping the array itself, each friend i take a subarray (l_i, r_i) from the array and kept it in a safe place, and get rid of the rest of the array.

Now Husam has n subarrays from the array a, but he cannot remember the original array or even its length. Husam now needs your help again, he will give you the n subarrays, and your task is to build a new array a such that it contains all the given subarrays inside it as subarrays, and its length must be as minimal as possible. Can you?

The first line contains an integer n (1 ≤ n ≤ 15), where n is the number of friends Husam has.

Then n lines follow, each line i begins with an integer m_i (1 ≤ m_i ≤ 100), where m_i is the length of the subarray the i^th friend has. Then m_i integers follow, representing the i^th subarray. All values x in the subarrays are in the range (1 ≤ x ≤ 10⁹).

Print the minimal length of the new array a, such that a contains all the given subarrays in the input inside it as subarrays.

3
2 1 2
4 3 4 5 6
3 2 3 4

6

5
3 4 7 5
4 7 9 2 5
3 7 5 2
4 5 1 4 7
4 9 2 5 1

9

A subarray of the array a is a sequence a_l, a_l + 1, ..., a_r for some integers (l, r) such that (1 ≤ l ≤ r ≤ n).

In the first test case the array a can be [1, 2, 3, 4, 5, 6]. Its length is as minimal as possible, and it contains all the the given subarrays in the input inside it as subarrays.