刷题群有一个左右弟，他每波刷题时总是希(xī)望(wàng)左右哥带带他。实力为0的左右弟一共经历了n波刷题，经过总结，发现第i次刷题时他自己做那么实力会增加a_i；让左右哥带他他的实力会变为b_i倍。
经过n次刷题之后，左右弟幡然悔悟：如果能重新再来，我一定！一定！！要！！！贪心一些先算算哪些次不让左右哥带最终实力最高。
如果真的可以重来，左右弟的实力最高是多少？
第一行，一个正整数n。
接下来n行，每行两个整数a_i,b_i。
对于100%的数据：
1\le n \le 5×10^5；
1\le a_i,b_i \le 10^9。
一个整数，表示左右弟能达到的最大实力值对19980829取模的结果。
4 1 10 5 4 5 2 3 1
15
样例一解释：
0+1
1+5
6*2
12+3
| 时间限制 | 1000 毫秒 |
| 内存限制 | 128 MB |