当前没有测试数据。

Ex - 骰子之和2

分数：$600$ 点

问题描述

六面骰子专卖店“Saikoroya”出售$N$个骰子。第$i$个骰子（复数为骰子）上分别写有$A_{i,1},A_{i,2},\ldots,A_{i,6}$，并且价格为$C_i$。

Takahashi将要选择其中的$K$个骰子并购买。

目前，“Saikoroya”正在进行促销：Takahashi可以掷每个已购买的骰子一次，并声称金额等于骰子所示数字之和的平方。此处，每个骰子均以均匀且独立的方式显示六个数字之一。

通过适当选择要购买的$K$个骰子，最大化（他所要求的金额）-（他为购买的$K$个骰子所支付的金额）的期望值。输出最大化的期望值模$998244353$。

约束条件

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

输入

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

$N$ $K$

$C_1$ $C_2$ $\ldots$ $C_N$

$A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,6}$

$\vdots$

$A_{N,1}$ $A_{N,2}$ $\ldots$ $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$个骰子，则（他所要求的金额）-（他为购买的$K$个骰子所支付的金额）的期望值等于$(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