P16239 [Lanqiao Cup 2026 NOI Qualifier B] Football Training

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.: $$ \prod_{i=1}^{n} (a_i + k_i b_i) $$ where $k_i$ is the number of training days assigned to player $i$, and it satisfies: $$ k_i \ge 0, \quad \sum_{i=1}^{n} k_i = m $$ 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$.

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 one line containing one non-negative integer, representing the maximum possible team strength after $m$ days of training, modulo $998244353$.

### 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