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.

utilForever 来到了寿司寿司（Sushisushi）回转寿司餐厅。其回转传送带共有 $N$ 个可放置寿司的位置。初始时，第 $i$ 个位置上叠放着 $K_i$ 个寿司；在第 $i$ 个位置上，从上往下数第 $j$ 个寿司被吃掉时，带来的满足感为 $X_{i,j}$。注意：$X_{i,j}$ 可能为负数。

从今天的午餐开始，utilForever 将连续进食 $T$ 天。每天午餐时，utilForever 最多只能吃一个寿司，且只能吃位于第 $1$ 号位置的寿司堆中最上面的那个寿司。每晚传送带会向左移动一格：原来在第 $i+1$ 号位置的寿司移动到第 $i$ 号位置，而原来在第 $1$ 号位置的寿司则移动到第 $N$ 号位置。

求 utilForever 能获得的最大总满足感。

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}$

输入从标准输入中按以下格式给出：

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

输出 utilForever 能够获得的最大总满意度。

表示言語

/ /

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.

表示语言

/ /

约束条件

• $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$
• 所有输入值均为整数。