/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
表示言語
/ /Score : 100 points
Problem Statement
utilForever visited the Sushisushi conveyor belt sushi restaurant. Its conveyor belt has a total of N positions where sushi can be placed. Initially, K_i pieces of sushi are stacked at the i-th position, and eating the j-th sushi from the top at the i-th position gives satisfaction X_{i,j}. X_{i,j} may be negative.
Starting with today's lunch, utilForever will eat for T days. At lunch each day, utilForever can eat at most one sushi, namely the top sushi among the sushi at position 1. The conveyor belt moves by 1 position every night. Sushi that was at position i+1 moves to position i, and sushi that was at position 1 moves to position N.
Find the maximum possible total satisfaction utilForever can obtain.
Constraints
- 1 \leq N,T \leq 10^6
- 0 \leq K_i \leq 10^6
- \sum_{i=1}^N K_i \leq 10^6
- -100 \leq X_{i,j} \leq 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N T
K_1 X_{1,1} X_{1,2} \dots X_{1,K_1}
K_2 X_{2,1} X_{2,2} \dots X_{2,K_2}
\vdots
K_N X_{N,1} X_{N,2} \dots X_{N,K_N}
Output
Output the maximum possible total satisfaction utilForever can obtain.
Sample Input 1
4 10 5 31 4 -15 9 26 3 53 -5 -89 3 -79 -32 -38 0
Sample Output 1
88
表示言語
/ /점수 : 100 점
문제
utilForever는 스시스시 회전초밥집에 갔다. 스시스시 회전초밥집의 회전초밥 레일에는 초밥을 놓을 수 있는 칸이 N개 있다. 처음에 i번째 칸에는 초밥이 K_i개 쌓여 있으며, 그중 i번째 칸의 위에서 j번째 초밥을 먹으면 만족감을 X_{i,j}만큼 얻을 수 있다. X_{i,j}가 음수일 수도 있다.
utilForever는 오늘 점심부터 T일 동안 식사를 하려 한다. 매일 점심 utilForever는 1번 칸에 있는 초밥 중 가장 위에 있는 초밥을 최대 하나 먹을 수 있다. 회전초밥 레일은 매일 밤 1칸씩 이동한다. i+1번 칸에 있던 초밥은 i번 칸으로 이동하고 1번 칸에 있던 초밥은 N번 칸으로 이동한다.
utilForever가 얻을 수 있는 만족감의 합의 최댓값을 구해 보자.
제한
- 1 \leq N,T \leq 10^6
- 0 \leq K_i \leq 10^6
- \sum_{i=1}^N K_i \leq 10^6
- -100 \leq X_{i,j} \leq 100
- 입력으로 주어지는 수는 모두 정수이다.
입력
입력은 다음 형식으로 표준 입력으로 주어진다.
N T
K_1 X_{1,1} X_{1,2} \dots X_{1,K_1}
K_2 X_{2,1} X_{2,2} \dots X_{2,K_2}
\vdots
K_N X_{N,1} X_{N,2} \dots X_{N,K_N}
출력
utilForever가 얻을 수 있는 만족감의 합의 최댓값을 출력한다.
입력 예 1
4 10 5 31 4 -15 9 26 3 53 -5 -89 3 -79 -32 -38 0
출력 예 1
88
表示言語
/ /配点 : 100 点
問題文
utilForeverがスシスシ回転寿司店に行きました．その店の回転寿司レールには，寿司を置くことができる位置が全部で N 個あります．初め，i 番目の位置には K_i 個の寿司が積まれており，i 番目の位置の上から j 番目の寿司を食べると満足度を X_{i,j} 得ることができます．X_{i,j}が負になることがあります．
utilForeverは今日の昼食から T 日間食事をしようとしています．毎日昼食に utilForeverは 1 番目の位置にある寿司のうち，一番上にある寿司を高々 1 個食べることができます．回転寿司レールは毎晩 1 個分移動します．i+1 番目の位置にあった寿司は i 番目の位置へ移動し，1 番目の位置にあった寿司は N 番目の位置へ移動します．
utilForeverが得ることができる満足度の合計の最大値を求めてください．
制約
- 1 \leq N,T \leq 10^6
- 0 \leq K_i \leq 10^6
- \sum_{i=1}^N K_i \leq 10^6
- -100 \leq X_{i,j} \leq 100
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる．
N T
K_1 X_{1,1} X_{1,2} \dots X_{1,K_1}
K_2 X_{2,1} X_{2,2} \dots X_{2,K_2}
\vdots
K_N X_{N,1} X_{N,2} \dots X_{N,K_N}
出力
utilForeverが得ることができる満足度の合計の最大値を出力せよ．
入力例 1
4 10 5 31 4 -15 9 26 3 53 -5 -89 3 -79 -32 -38 0
出力例 1
88