骰子和 2

题目描述

六面骰子专卖店「骰子屋」出售 $N$ 个骰子。第 $i$ 个骰子的各面写有 $A_{i,1}, A_{i,2}, \ldots, A_{i,6}$，价格为 $C_i$。

高桥君打算恰好选择其中 $K$ 个购买。

现在，「骰子屋」正在开展促销活动：高桥君可以把购买的每个骰子各掷一次，获得金额等于所有骰子掷出的数字之和的平方的奖金。这里，每个骰子以均匀且独立的方式随机显示六个数字之一。

通过合理选择购买的 $K$ 个骰子，最大化（获得的奖金金额）-（购买这 $K$ 个骰子支付的费用之和）的期望值。输出最大化的期望值模 $998244353$ 的值。

模 $998244353$ 的期望值的定义

可以证明所求期望值始终是有理数。 此外，在本问题的数据范围内，所求期望值可以用不可约分数 $\frac{y}{x}$ 表示，其中 $x$ 不能被 $998244353$ 整除。

在这种情况下，可以唯一确定满足 $xz \equiv y \pmod{998244353}$ 的介于 0 到 $998244352$（含）之间的整数 $z$。输出这样的 $z$。

输入格式

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

N K
C_1 C_2 … C_N
A_{1,1} A_{1,2} … A_{1,6}
⋮
A_{N,1} A_{N,2} … A_{N,6}

输出格式

输出答案。

样例

3 2
1 2 3
1 1 1 1 1 1
2 2 2 2 2 2
3 3 3 3 3 3

20

如果购买第 2 个和第 3 个骰子，（获得的奖金金额）-（购买的骰子的费用之和）的期望值为 $(2 + 3)^2 - (2 + 3) = 20$，这是期望值的最大值。

10 5
2 5 6 5 2 1 7 9 7 2
5 5 2 4 7 6
2 2 8 7 7 9
8 1 9 6 10 8
8 6 10 3 3 9
1 10 5 8 1 10
7 8 4 8 6 5
1 10 2 5 1 7
7 4 1 4 5 4
5 10 1 5 1 2
5 1 2 3 6 2

1014

数据范围

• $1 \le N \le 1000$
• $1 \le K \le N$
• $1 \le C_i \le 10^5$
• $1 \le A_{i,j} \le 10^5$
• 输入中的所有值均为整数。