Background

Problem setter: XL4453.

Problem reviewer: 犇犇犇犇 (ben ben ben ben).

Statement writer: 小糯米 (xiao nuo mi).

upd: Note: take modulo first, then take $\max$.

Problem Description

"Don't mind it. Those guys and I are all salvagers. When we first chased our dreams and landed on the surface, we were already prepared to die and ready to face death."

During one salvage operation, Grick's team got lucky and obtained quite a lot of treasure. On the way back, when talking about who contributed the most, conflicts broke out. Some said their treasure was one of a kind in history, something they barely snatched back after walking right up to the gates of death; some said they worked hard for a long time—although they did not get something that precious, the quantity was impressive and could still be compared with that; others said their gains had both quality and quantity and should be evaluated in a combined way. In short, everything became chaotic, and there was even a risk that companions who once shared life and death would split apart.

So everyone turned to Grick, which put him in a difficult spot. After thinking for a long time, he decided to evaluate everyone's contribution like this:

Suppose there are $n$ salvagers in total. The $i$-th salvager $a_i$ obtained $l_i$ treasures, and the value of the $p$-th treasure is $a_{i,p}$. Then, when calculating, you only need to add up each sequence and sum them. But Grick is not satisfied with the current situation. Now he wants to know: if we look at the contributions of two people together, how should we calculate it?

After an intense brainstorming session, he decided to define the contribution between two salvagers $i, j$ as $g(i,j)$: copy $a_i$ and $a_j$ several times so that both piles have $k$ treasures, obtaining two sequences $a_i', a_j'$. Then $g(i,j)= \sum\limits_{p=1}^k a'_{i,p}\times a'_{j,p}$.

Now Grick wants to know what the maximum contribution value is.

Because the contribution value may be very large and exceed normal brain computing ability, we take it modulo $998244353$.

Formal statement: Given an integer $n$ and $n$ sequences. The $i$-th sequence $\{a_i\}$ has length $l_i$. Copy each $a_i$ $\dfrac k{l_i}$ times to obtain $\{a'_i\}$ so that $\{a'_i\}$ has length $k$.

Find: $\max\limits_{i=1,j=i+1}^{i,j\leq n}\{g(i,j)\bmod 998244353\}$, where $g(i,j)= \sum\limits_{p=1}^k a'_{i,p}\times a'_{j,p}$.

Input Format

The first line contains two integers $n$, $k$.

Then follow $n$ lines. On line $i + 1$, the first number is $l_i$, followed by $l_i$ numbers representing salvager $i$'s treasures $a_i$.

Output Format

One integer, representing the required maximum value.

2 12
3 2 3 4
4 1 2 3 4

90

3 999999924
4 4 4 5 3
7 1 9 1 9 8 1 0
6 1 1 4 5 1 4

599517664

Hint

Sample Explanation #1

$a_1'=2, 3, 4, 2, 3, 4, 2, 3, 4, 2, 3, 4$.
$a_2'=1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4$.
$g(1,2)=2\times1+3\times2+4\times3+2\times4+3\times1+4\times2+2\times3+3\times4+4\times1+2\times2+3\times3+4\times4=90$.

Sample Explanation #2

$g(1,2)\bmod998244353=599517664$.
$g(1,3)\bmod998244353=350889018$.
$g(2,3)\bmod998244353=66930325$.
$\max\limits_{1\leq i < j \leq n}\{g(i,j)\bmod998244353\}=599517664$.

Constraints

For $10\%$ of the testdata, $n=2$.
For $30\%$ of the testdata, $k \leq 100$.
For $60\%$ of the testdata, all $l_i$ are pairwise coprime, i.e. $\gcd(l_i,l_j)=1(1\leq i < j \leq n)$, where $\gcd$ is the greatest common divisor.
For $100\%$ of the testdata, $1\leq n\le 100，1\leq l_i\le 1000，1\leq k,a_{i,j}\le 10^{9}$, and for any $i \in [1,n]$, $l_i\mid k$.

Translated by ChatGPT 5