cats 的快乐 CF 刷题

Problem Description

此题输入/输出量较大，建议使用较快的读入方式，时间限制以关闭流同步的 cin/cout 为标准 cats 非常喜欢在 CF(CatForces) 上做好玩的题。今天 CF 更新了 $n$ 个新的题，cats 希望通过一定的顺序来做这些题以获得尽可能更多的快乐值。 这 $n$ 个题被从左到右排列在一个双端队列中，其中从左到右的第 $i$ 个题具有难度 $a_i$ 和趣味度 $b_i$。cats 有一个能力值 $d$，初始为 $0$。cats 可以不断的选择去做双端队列中最左侧或者最右侧的题，然后将其从双端队列中移除，直到做完全部的 $n$ 个题为止。 在做题的过程中，cats 可以收获快乐。如果 cats 当前的能力值为 $d$，当 cats 做一个难度为 $A$，趣味度为 $B$ 的题时，以下两件事情会按下面的顺序依次发生：

1. cats 的能力值增加 $A$。即 $d:=d+A$。
2. cats 获得 $d\cdot B$ 点快乐值。 现在，cats 想通过合理的安排做这 $n$ 个题的顺序来获得尽可能多的快乐值。你需要求出 cats 在做题过程中可以获得的快乐值总和的最大值。

Input

第一行包含一个整数 $T$ $(1\leq T \leq 10^4)$，表示一共有 $T$ 组测试数据。 每组测试数据的第一行包含一个整数 $n$ $(1\leq n\leq 2\cdot 10^5)$，表示 CF 题的总数。 接下来 $n$ 行，每行包含 $2$ 个整数 $a_i,b_i$ $(0\leq a_i,b_i\leq 10^4)$，表示双端队列中从左到右第 $i$ 个题的难度和趣味度。 保证所有测试数据的 $n$ 之和不超过 $10^6$。

Output

对于每组测试数据，输出一个整数，表示 cats 在做题过程中可以获得的快乐值总和的最大值。

Sample Input

3
1
314 159
3
1 1
1 2
2 1
3
1 1
2 1
1 2

Sample Output

49926
13
12

Source

2024“钉耙编程”中国大学生算法设计超级联赛（8）