Problem Description

Xiaolan is the captain of a football team, and he is preparing for the next important match. Over the next $m$ days, each day he can choose one player to train, and once chosen, the training target for that day cannot be changed.

There are $n$ players in the team. For player $i$, we know:

• The initial strength value is $a_i$.
• The talent value is $b_i$.

The training rules are as follows:

• If Xiaolan trains player $i$ on some day, then on that day the player’s strength value increases by $b_i$.
• If player $i$ is trained for a total of $k$ days, then the player’s final strength value becomes: $a_i + k b_i$.

The overall strength of the team is defined as the product of all players’ final strength values, i.e.:

where $k_i$ is the number of training days assigned to player $i$, and it satisfies:

Xiaolan hopes to maximize the team’s overall strength by allocating these $m$ training days reasonably. Since the result may be very large, you only need to output the maximum value modulo $998244353$.

Input Format

The input has $n+1$ lines.

The first line contains two positive integers $n, m$, representing the number of players and the total number of days available for training.

The next $n$ lines each contain two positive integers $a_i, b_i$, representing the initial strength value and the talent value of player $i$.

Output Format

Output one line containing one non-negative integer, representing the maximum possible team strength after $m$ days of training, modulo $998244353$.

2 3
4 2
5 3

66

Hint

Sample Explanation

One optimal plan is:

• Train player $1$ for $1$ day.
• Train player $2$ for $2$ days.

Then:

• Player $1$’s final strength is $4 + 2 \times 1 = 6$.
• Player $2$’s final strength is $5 + 3 \times 2 = 11$.

The team’s overall strength is $6 \times 11 = 66$, so the output is $66$.

Constraints

For $30\%$ of the testdata, $n, m \le 8$.

For $60\%$ of the testdata, $n, m, a_i, b_i \le 3000$.

For $100\%$ of the testdata, $1 \le n \le 100000$, $1 \le m \le 10^9$, $1 \le a_i, b_i \le 10^5$.

Translated by ChatGPT 5