交与并

时间限制:10s      空间限制:128MB

题目描述

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

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


输入格式

    给你N个各不相同的区间,请你从中找出若干个区间使其权值最大。

 

 第一行N

 接下来Nl 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.

提示

100%  1<N<=10^6


题目来源

没有写明来源