P16239 [蓝桥杯 2026 省 B] 足球训练

小蓝是一支足球队的队长，他正在为下一场重要比赛做准备。接下来的 $m$ 天中，他每天可以选择一名队员进行训练，并且选择之后当天的训练对象不能更换。 球队中共有 $n$ 名队员。对于第 $i$ 名队员，已知其： - 初始实力值为 $a_i$； - 天赋值为 $b_i$。 训练规则如下： - 如果小蓝在某一天训练了队员 $i$，则这一天会使该队员的实力值增加 $b_i$； - 如果一共用 $k$ 天来训练队员 $i$，那么这名队员的最终实力值将变为：$a_i + k b_i$。 一支队伍的整体实力定义为所有队员最终实力值的乘积，即： $$ \prod_{i=1}^{n} (a_i + k_i b_i) $$ 其中 $k_i$ 表示分配给第 $i$ 名队员的训练天数，且满足： $$ k_i \ge 0, \quad \sum_{i=1}^{n} k_i = m $$ 小蓝希望通过合理分配这 $m$ 天的训练计划，使得队伍的整体实力最大。由于结果可能非常大，你只需要输出该最大值对 $998244353$ 取模的结果。

输入共 $n+1$ 行。 第一行包含两个正整数 $n, m$，分别表示队员人数和可用于训练的总天数。 接下来 $n$ 行，第 $i$ 行包含两个正整数 $a_i, b_i$，表示第 $i$ 名队员的初始实力值与天赋值。

输出一行，包含一个非负整数，表示经过 $m$ 天训练后，队伍实力的最大可能值对 $998244353$ 取模的结果。

### 【样例说明】 一种最优方案是： - 第 $1$ 名队员训练 $1$ 天； - 第 $2$ 名队员训练 $2$ 天。 此时： - 第 $1$ 名队员的最终实力为 $4 + 2 \times 1 = 6$； - 第 $2$ 名队员的最终实力为 $5 + 3 \times 2 = 11$。 队伍的整体实力为：$6 \times 11 = 66$，因此输出 $66$。 ### 【评测用例规模与约定】 对于 $30\%$ 的数据，$n, m \le 8$； 对于 $60\%$ 的数据，$n, m, a_i, b_i \le 3000$； 对于 $100\%$ 的数据，$1 \le n \le 100000$，$1 \le m \le 10^9$，$1 \le a_i, b_i \le 10^5$。