3795: 同色三角形(第四轮01)

内存限制:256 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:1 解决:1

题目描述

有一个 n  个点的完全图,点分别被编号为  1 ~ n ,每个点都有 n − 1  条边连向其它点。每 条边有绿色或者红色两种颜色,现在我们知道每个点连着几条绿色边,几条红色边,但不知 道每条边具体连接哪个点。

在完全图中任选三个点,观察它们之间的三条边,如果三条边颜色相同,那么我们就称其为  “同色三角形”。现在牛牛已经知道了每个点连着几条绿色、红色边(保证这样的图一定存在), 他想要知道图中最多有几个同色三角形。

很可惜,牛牛是色盲,所以这个问题只能交给你了。

大样例:sample.zip

输入

第一行输入一个正整数 n,表示共有 n  个点。

 

接下来包含 n  行,每行给两个数字 a, b,其中第  i  行的数字表示第  i  个点的红色边、绿 色边数量,保证 a + b = n − 1

输出

输出一行一个整数表示答案。

样例输入 复制

4
1 2
2 1
2 1
3 0

样例输出 复制

1

提示

【说明】

【备注】

对于  10% 的数据,有 n = 3

对于 20%  的数据,有 n = 4   

对于 30%  的数据,有 n = 5    对于 50% 的数据,有 n  ≤  20

对于 70%  的数据,有 n  ≤  1000

对于  100% 的数据,有  3  ≤  n   ≤  3 *  10^5


来源/分类