队爷的新书

题目描述

队爷即将出版新书,以记录他辉煌的虐题生涯。。。 有 $n$ 家出版社对这本书表示了兴趣,并愿意给队爷支付 $p \in [Min_{pay},Max_{pay}]$ 的报酬来得到这本书的出版权,每家出版社的 $Min_{pay}$ 和 $Max_{pay}$ 是不一样的。 现在队爷希望你帮他找出一个报酬值 $p$,使得他获得的总报酬最多。(每一个 $Min_{pay} \leq p \leq Max_{pay}$ 的出版社都会付给队爷 $p$ 的报酬)。

输入输出格式

输入格式


第一行为一个整数 $n$。 接下来 $n$ 行,每行 $2$ 个整数 $Min_{payi}$ 和 $Max_{payi}$,为第 $i$ 家出版社愿支付的报酬范围。

输出格式


只有一个整数 ans,为最大总报酬。

输入输出样例

输入样例 #1

4
1 3
2 4
3 5
4 7

输出样例 #1

12

说明

【样例解释】 当 $p = 4$ 时,有 $3$ 家出版社会给出报酬,此时最大。 【数据规模与约定】 对于 $20\%$ 的数据,$1 \leq Min_{pay},Max_{pay} \leq 10000$; 对于 $40\%$ 的数据,$1 \leq n \leq 1000,1 \leq Min_{pay},Max_{pay} \leq 10^6$; 对于 $100\%$ 的数据,$1 \leq n \leq 100000,1 \leq Min_{pay},Max_{pay} \leq 10^9$。