Buying Jewels

A jewel shop displays jewels in several rows. Each jewel has an integer value, and a cursed jewel may have a negative value.

There are n rows of jewels. For each row, you must choose one non-empty contiguous segment and buy all jewels in that segment. For example, in one row you may buy jewels 1 and 2 together, or jewels 2 and 3 together, but you may not buy only jewels 1 and 3.

Write a program that chooses the segment to buy in every row so that the total value of all purchased jewels is maximized.

The first line contains an integer n (1 ≤ n ≤ 1,000).

The next 2×n lines describe the rows of jewels. For each row, the number of jewels L (1 ≤ L ≤ 1,000) is given on one line, and the next line contains L integers representing the jewel values. Each value is an integer whose absolute value is at most 10,000.

On the first line, print the maximum possible total value of the purchased jewels.

Then print n lines. Each line must contain the first and last jewel positions bought from the corresponding row.

If multiple choices achieve the maximum total value, print one that buys the smallest total number of jewels. If there are still multiple choices, consider the printed n×2 numbers as one sequence and print the lexicographically smallest such sequence.