题目描述

小蓝是一支足球队的队长，他正在为下一场重要比赛做准备。接下来的 $m$ 天中，他每天可以选择一名队员进行训练，并且选择之后当天的训练对象不能更换。

球队中共有 $n$ 名队员。对于第 $i$ 名队员，已知其：

• 初始实力值为 $a_i$；
• 天赋值为 $b_i$。

训练规则如下：

• 如果小蓝在某一天训练了队员 $i$，则这一天会使该队员的实力值增加 $b_i$；
• 如果一共用 $k$ 天来训练队员 $i$，那么这名队员的最终实力值将变为：$a_i + k b_i$。

一支队伍的整体实力定义为所有队员最终实力值的乘积，即：

其中 $k_i$ 表示分配给第 $i$ 名队员的训练天数，且满足：

小蓝希望通过合理分配这 $m$ 天的训练计划，使得队伍的整体实力最大。由于结果可能非常大，你只需要输出该最大值对 $998244353$ 取模的结果。

输入格式

输入共 $n+1$ 行。

第一行包含两个正整数 $n, m$，分别表示队员人数和可用于训练的总天数。

接下来 $n$ 行，第 $i$ 行包含两个正整数 $a_i, b_i$，表示第 $i$ 名队员的初始实力值与天赋值。

输出格式

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

2 3
4 2
5 3

66

提示

【样例说明】

一种最优方案是：

• 第 $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$。