Fast Fingers Thomas is eating poutine at Wilson's restaurant. Thomas has ~T~ dollars, and an order of poutine at Wilson's restaurant costs one dollar. Consequently, Thomas can place at most ~T~ orders of poutine.

There are ~N~ different types of poutine that Thomas can order. If Thomas orders poutine ~i~ for the first time, he gains ~a_i~ units of happiness. If Thomas orders poutine ~i~ for the ~k~th time, he gains ~\max(0, a_i - (k-1)b_i)~ units of happiness. Wilson will never run out of any type of poutine.

Compute the maximum amount of happiness Thomas can feel after eating some amount of poutine.

Constraints

~1 \le N \le 10^5~

~1 \le a_i, b_i, T \le 10^{18}~

Input Specification

The first line of input contains two positive integers, ~N~ and ~T~.

Each of the next ~N~ lines contains two space-separated integers, ~a_i~ and ~b_i~ for poutine ~i~.

Output Specification

Let ~g~ be the maximum attainable units of happiness that Thomas can feel. Output ~g~ modulo ~998\,244\,353~.

Sample Input

2 3
8 2
7 2

Sample Output

21