Maximum Sum

Time limit1sMemory limit128 MB

Summary

Given n boxes of numbered balls, pick at most one ball per box in order to form a non-decreasing sequence with maximum possible sum.

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

Problem

You are given a sequence of $n$ boxes. Each box contains several balls, and every ball has a whole number written on it.

You choose some of the boxes (one, several, or all of them) and take exactly one ball from each chosen box, keeping the boxes in their original order. Arranging the taken balls in that order gives a sequence of numbers. Consider only the choices for which this sequence is non-decreasing (each number is at least the previous one), and compute the largest possible sum of the taken numbers.

Input

The first line contains $n$ . Each of the following $n$ lines describes one box: it begins with the number of balls in that box, followed by the numbers written on those balls.

Output

Output a single integer: the maximum sum described above.

Constraints

$0 < n < 500$ . Each box contains at least one ball and no more than $50$ balls. Every number written on a ball is between $1$ and $1000$ , inclusive.

Examples1

Example 1

Input

10
3 2 2 4
2 1 2
3 3 7 10
4 5 5 1 1
1 3
1 2
3 1 9 1
1 5
7 8 1 1 1 1 2 1
1 3

Expected output