2313번 - 보석 구매하기

보석 가게에 여러 가지의 보석이 진열되어 있다. 각각의 보석은 정수로 표현되는 가치가 있다. 때로는 저주받은 보석이 있기 때문에 가치가 음수가 될 수도 있다.

보석들은 총 n개의 줄에 나열되어 있다. 이제 당신은 각각의 줄에서 몇 개의 보석을 구매하려 한다. 이때, 각 줄에서 보석을 구매할 때 연속적인 보석들을 구매해야 한다. 즉, 어느 한 줄에서 1, 2번 보석을 구매할 수도 있고, 2, 3번 보석을 구매할 수도 있지만, 1, 3번 보석을 구매할 수는 없다.

구매하는 보석의 가치의 총 합이 최대가 되도록 보석을 구매하는 방법을 찾아내는 프로그램을 작성하시오.

첫째 줄에 정수 n(1≤n≤1,000)이 주어진다. 다음 2×n개의 줄에는 n개의 줄에 나열된 보석들에 대한 정보가 주어진다. 먼저 각 줄에 나열된 보석의 개수 L(1≤L≤1,000)이 주어지고, 그 다음 줄에 L개의 정수들이 주어진다. 각 정수는 각 보석의 가치를 나타낸다.

첫째 줄에 보석의 가치의 총 합의 최댓값을 출력한다. 다음 n개의 줄에는, 줄에서 몇 번째 보석부터 몇 번째 보석까지를 구매했는지를 출력한다.

만약 최대가 되는 경우가 여럿이면, 구매한 보석들의 총 개수가 최소가 되는 방법을 출력한다. 이와 같은 경우도 여럿이라면, 출력한 n×2개의 수들을 하나의 수열로 생각하여, 사전식으로 가장 앞에 오는 경우를 출력한다.