此题输入/输出量较大，建议使用较快的读入方式，时间限制以关闭流同步的 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$ 的题时，以下两件事情会按下面的顺序依次发生：

• cats 的能力值增加 $A$。即 $d:=d+A$。
• cats 获得 $d⋅B$ 点快乐值。

现在，cats 想通过合理的安排做这 $n$ 个题的顺序来获得尽可能多的快乐值。你需要求出 cats 在做题过程中可以获得的快乐值总和的最大值。

第一行包含一个整数 $T(1≤T≤10^4)$，表示一共有 $T$ 组测试数据。

每组测试数据的第一行包含一个整数 $n(1≤n≤2⋅10^5 )$，表示 CF 题的总数。

接下来 $n$ 行，每行包含 $2$ 个整数 $a_i,b_i((0≤a_i,b_i ≤10^4 )$，表示双端队列中从左到右第 $i$ 个题的难度和趣味度。

保证所有测试数据的 $n$ 之和不超过 $10^6$ 。

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