题目描述
对于一个区间集合 A1,A2,…,Ak(k>1 且 ∀i=j,Ai=Aj),定义其权值 S=∣∪i=1kAi∣×∣∩i=1kAi∣
即它们的交区间的长度乘上它们并区间的长度。
显然,如果这些区间没有交集则权值为 0。
Your Task:给定你若干互不相等的区间,选出若干区间使其权值最大。
输入格式
第一行 n 表示区间的个数。
接下来 n 行每行两个整数 l,r 描述一个区间 [l,r]。
输出格式
在一行中输出最大权值。
样例输入
4
1 6
4 8
2 7
3 5
样例输出
24
样例说明
选择 [1,6] 和 [2,7] 是最优的。
数据规模与约定
对于 100% 的数据,1<N≤106,1≤L<R≤106。