Cheapest Route to a Heavenly Planet

Thomas lives on a planet of level \(0\), where the harsh environment, 12 hours of work a day, and piles of garbage make life unbearable. He dreams of a heavenly existence on a planet of level \(N\).

There are flights that take people from a lower-level planet to the next higher-level planet. Sometimes, you need to pay the pilot, and sometimes you even get paid. Thomas knows in advance all the available flights from his level \(0\) planet to the destination planet of level \(N\), along with the associated cost (or gain). He wants to find the route that minimizes the total cost (or maximizes the money he can earn if the overall cost is negative).

Note: Each flight connects planet level \(i\) to planet level \(i+1\) (\(0 \le i \lt N\)). For each leg, there can be multiple flight options. The cost of a flight may be negative, which means you earn money on that leg.

inputFormat

The first line contains a single integer \(N\) (the number of legs, i.e. the destination planet is level \(N\)).

Then follow \(N\) lines. The \(i\)-th of these lines (for \(0 \le i \lt N\)) starts with an integer \(k\) indicating the number of flights available from planet level \(i\) to planet level \(i+1\), followed by \(k\) space-separated integers representing the cost of each flight.

outputFormat

Output a single integer representing the minimum total cost to travel from planet level \(0\) to planet level \(N\). This total cost is the sum of the minimum flight cost chosen for each leg.

sample

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

-6