logo AlgoBeat OnlineJudge
登录 注册

#102687. [BZOJ 2687] 交与并

内存限制:128 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

对于一个区间集合{A1,A2……AK}(K>1,Ai<>Aj{i<>j}),我们定义其权值

W=|A1∪A2∪……∪AK|*|A1∩A2∩……AK|当然,如果这些区间没有交集则权值为0。

输入格式

给你N个(1<N<=10^6)各不相同的区间,请你从中找出若干个区间使其权值最大。

第一行N,接下来N行 l r(1<=l<r<=10^6)

输出格式

最大权值

样例

样例输入

4
1 6
4 8
2 7
3 5

样例输出

24
样例注释:选择第1个和第3个区间,交为(2,6),并为(1,7),权值为4*6=24.