보석 구매하기

보석 가게에는 여러 줄에 걸쳐 보석이 진열되어 있다. 각 보석에는 정수로 나타낸 가치가 있으며, 저주받은 보석은 음수의 가치를 가질 수도 있다.

보석은 모두 n개의 줄에 놓여 있다. 각 줄마다 비어 있지 않은 연속 구간 하나를 골라 그 구간의 보석을 구매하려고 한다. 예를 들어 한 줄에서 1번과 2번 보석을 함께 살 수 있고, 2번과 3번 보석을 함께 살 수도 있지만, 1번과 3번 보석만 따로 살 수는 없다.

구매한 모든 보석의 가치 합이 최대가 되도록 각 줄에서 살 구간을 정하는 프로그램을 작성하시오.

첫째 줄에 정수 n (1 ≤ n ≤ 1,000)이 주어진다.

이후 2×n개의 줄에 각 줄의 보석 정보가 주어진다. 각 보석 줄마다 먼저 보석의 개수 L (1 ≤ L ≤ 1,000)이 한 줄에 주어지고, 다음 줄에 보석의 가치를 나타내는 L개의 정수가 주어진다. 각 보석의 가치는 절댓값이 10,000 이하인 정수이다.

첫째 줄에 구매한 보석 가치 합의 최댓값을 출력한다.

다음 n개의 줄에는 각 줄에서 몇 번째 보석부터 몇 번째 보석까지 구매했는지를 출력한다.

최댓값을 만드는 방법이 여러 가지라면, 구매한 보석의 총 개수가 가장 적은 방법을 출력한다. 그런 방법도 여러 가지라면, 출력되는 n×2개의 수를 하나의 수열로 보았을 때 사전순으로 가장 앞서는 방법을 출력한다.