3914번 - Maximum Sum 다국어

Given is a sequence of n boxes. In each box, there are several balls. On each ball is written one whole number. We choose some (1, 2, ...,, or all) boxes and take one ball from each one of the chosen boxes, keeping the order of the boxes. Then we arrange all taken balls in a line, according to the order of the boxes. Sometimes, the numbers written on the taken balls may form a non-decreasing sequence. Write program maxsum, which computes what may be the largest sum of these numbers.

The first line contains the value of n. It is followed by n lines, each corresponding to a box. Each of these lines begins with the quantity of balls in the box and then – the numbers written on the balls in this box.

One integer equals to the maximum sum, as is described above.

0 < n < 500. In each box, there are no more than 50 balls, but at least one. Any whole number, written on a ball, is in a range from 1 till 1000.

The sequence of taken balls is 2 + 2 + 3 + 5 + 5 + 8. From the 5th, 6th, 7th and 10th boxes, nothing is taken.