题目描述

现在有 $n$ 种木棍，第 $i$ 种木棍的长度为 $a_i$，共有 $b_i$ 根。 从这些木棍中取出三根（可以来自同一长度的多根）组成三角形，请问存在多少种 本质不同 的非退化三角形。

• 非退化三角形：三条边长度满足任意两边之和大于第三边。
• 本质不同：若两三角形不是全等（即边长的多重集合不同），则认为本质不同。也就是说，我们把三条边排序为 $x\le y\le z$，不同的 $(x,y,z)$ 计为不同三角形。

注意：取三根木棍时必须满足每种长度使用的根数不超过该长度的库存 $b_i$。

输入格式

输入包含多组测试数据。

第一行包含一个整数 $t$，表示测试数据组数。接下来的每组数据格式如下：

• 第一行输入一个整数 $n$，表示木棍的种类数。
• 接下来 $n$ 行，每行包含两个整数 $a_i\ b_i$，表示第 $i$ 种木棍长度为 $a_i$，有 $b_i$ 根。

输入保证所有 $a_i$ 互不相同。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示可以得到的本质不同的非退化三角形的最大数量。

样例输入 1

2
3
2 2
3 1
4 1
2
2 3
3 3

样例输出 1

2
4

样例 2

见选手目录下的 triangle/triangle2.in 与 triangle/triangle2.ans。 该测试用例满足测试点 $1\sim 3$ 的约束条件。

样例 3

见选手目录下的 triangle/triangle3.in 与 triangle/triangle3.ans。 该测试用例满足测试点 $4$ 的约束条件。

样例 4

见选手目录下的 triangle/triangle4.in 与 triangle/triangle4.ans。 该测试用例满足测试点 $5$ 的约束条件。

样例 5

见选手目录下的 triangle/triangle5.in 与 triangle/triangle5.ans。 该测试用例满足测试点 $6\sim 7$ 的约束条件。

样例 6

见选手目录下的 triangle/triangle6.in 与 triangle/triangle6.ans。 该测试用例满足测试点 $8\sim 10$ 的约束条件。

说明

样例解释

• 第 $1$ 组数据：可以组成的本质不同三角形为 $(2,2,3)$ 和 $(2,3,4)$，共 $2$ 种。
• 第 $2$ 组数据：长度 $2$ 有 3 根，长度 $3$ 有 3 根，可以得到的不同三角形为 $(2,2,2),(2,2,3),(2,3,3),(3,3,3)$，共 $4$ 种。

数据范围

对于 $100\%$ 的数据，满足：

• $1\le t\le 5$，
• $1\le n\le 5000$，
• $1\le a_i,b_i\le 10^9$，且所有 $a_i$ 互不相同。

各测试点的附加限制如下表所示：

• 特殊性质 A：所有 $b_i$ 均为 $1$。
• 特殊性质 B：所有 $b_i$ 均为 $2$。

大样例

点击下载