Another Contest 1 Problem 3 - Poutine

View as PDF

Submit solution


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

Problem type

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 ai units of happiness. If Thomas orders poutine i for the kth time, he gains max(0,ai(k1)bi) 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

1N105

1ai,bi,T1018

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, ai and bi for poutine i.

Output Specification

Let g be the maximum attainable units of happiness that Thomas can feel. Output g modulo 998244353.

Sample Input

Copy
2 3
8 2
7 2

Sample Output

Copy
21

Comments

There are no comments at the moment.