Another Contest 1 Problem 3 - Poutine

View as PDF

Submit solution


Points: 10
Time limit: 0.6s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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

Comments

There are no comments at the moment.