You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

卡牌游戏

题目背景

改编题

题目描述

小白兔和小黑兔在玩卡牌游戏。

小黑兔准备了$n$张卡牌，每张卡牌上有一个红色数字$a_i$，代表这张卡片的分数，和一个蓝色的标记×$b_i$，代表选择这张卡片时的得分倍率。

游戏规则是，小白兔每次可以选择一张卡片x，它在这次选择中可以获得的分数是：所有未被选择卡片的红色数字之和，乘上这次选择的卡片的蓝色数字，即$b_x×\sum\limits_{卡片i未被选择}a_i$。注意：卡片x在当次计分时即被视为已选择，如有疑问请看下面的样例解释。

对于上面的这个规则，小白兔很容易就找到了最优方案，小黑兔很不满，所以它决定加大游戏难度。

这次，小白兔的面前从$n$张牌变成了$n$叠牌，每一叠牌都只能取最上面的一张，取走上一张牌才能取下一张。除此之外，其他地方还是相同的，也就是说，数字$a_i$仍然代表分数，$b_i$仍然代表得分倍率。每次取卡x的分数还是$b_x×\sum\limits_{卡片i未被选择}a_i$。

这次的问题难倒了小白兔，它找到了你，希望你可以编写一个程序帮他找到最大的总分。同样地，由于总分可能很大，小白兔只需要知道这个分数模998244353的结果。

输入格式

第一行一个正整数$n$代表有$n$叠牌。

以下有$n$组数据代表$n$叠牌的情况。

对每组数据，第一行是一个正整数$m$，代表这叠牌有$m$张。

下面$m$行，每行两个正整数$a_i$和$b_i$，分别代表从上到下第$i$张牌的得分和得分倍率。

输出格式

一个正整数，代表最大总得分模998244353的结果。

样例 #1

样例输入 #1

2
1
1 1
2
4 5
1 4

样例输出 #1

14

样例输入 #2

见文件cardtwo.in

样例输出 #2

见文件cardtwo.out

提示

样例1解释：

样例1中依次取第2堆第1张牌（获得5*（1+1）=10分），第2堆第2张牌（获得4*1=4分），第1堆第1张牌，可以获得14分，是最大的总得分。

数据范围

对30%的数据满足$1\le n \le 100,1\le m\le 10$

对另外10%的数据满足$n=1$

对另外10%的数据满足$n=2$

对100%的数据，$1\le n \le 10^6,1\le\sum m\le 10^6,1\le a_i \le 10^5,1\le b_i\le 100$

记得开long long