AT_scpc2026_div3_d Sushisushi Conveyor Belt Sushi Restaurant

#### 表示言語 / / 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.

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 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.