bzoj#P2369. 区间

区间

题目描述

对于一个区间集合 A1,A2,,Ak{A_1,A_2,\dots,A_k}k>1k>1ij,AiAj\forall i\ne j,A_i\ne A_j),定义其权值 S=i=1kAi×i=1kAiS=|\cup_{i=1}^k A_i|\times|\cap_{i=1}^k A_i|

即它们的交区间的长度乘上它们并区间的长度。

显然,如果这些区间没有交集则权值为 00

Your Task:给定你若干互不相等的区间,选出若干区间使其权值最大。

输入格式

第一行 nn 表示区间的个数。

接下来 nn 行每行两个整数 l,rl,r 描述一个区间 [l,r][l,r]

输出格式

在一行中输出最大权值。

样例输入

4
1 6
4 8
2 7
3 5

样例输出

24

样例说明

选择 [1,6][1,6][2,7][2,7] 是最优的。

数据规模与约定

对于 100%100\% 的数据,1<N106,1L<R1061<N\le 10^6,1\le L<R\le 10^6