408525: GYM103181 F Relay Race

This year at the Olympics a new event was introduced: the mixed distance relay race. In this event, all of the athletes from each delegation try to run a $$$D$$$ meter race as fast as possible. Compared to the traditional competitions, there is one key difference: each team decides how to split the total distance among all of its runners.

The rules are:

• The athletes must run a total distance of $$$D$$$ meters.
• Each athlete starts running as soon as the previous teammate finishes his split.
• Each athlete must run an integer amount of meters.
• Each athlete must run at least 1 meter.
• The delegation's time is the sum of all individual runners' times.

As the chief strategist of your country's delegation, you must come up with a way of splitting the distance such that the total time is as small as possible.

You know that your delegation is composed of $$$N$$$ runners. Each one of them is characterized by two numbers: an initial speed, $$$a_i$$$, and a slowing down rate, $$$b_i$$$.

Initially, runner $$$k$$$ can advance a meter in $$$a_k$$$ seconds and, after that, each subsequent meter takes $$$b_k$$$ more seconds than the previous one. To be precise, the time it takes for athlete $$$k$$$ to run the $$$j^{th}$$$ meter is $$$a_k + b_k * (j - 1)$$$.

Knowing all the details about your delegation, you are asked to compute the smallest amount of time you could obtain with a valid way of splitting the distance among your athletes.

The first line of the input contains $$$2$$$ integers: $$$1 \leq N \leq 10^5$$$, the number of runners in the delegation, and $$$N \leq D \leq 10^9$$$, the length of the race.

Each of the following $$$N$$$ lines contains two integers $$$1 \leq a_i \leq 10^9$$$ and $$$1 \leq b_i \leq 10^9$$$, the description of each runner.

The output should contain one integer, representing the minimum possible time to complete the race. Since the value might become too large, print the result modulo $$$998244353$$$.

3 9
2 3
1 3
4 1

41

3 3
2 3
1 3
4 1

7