本周日是拜特镇（Bytetown）最重要的年度节日——字节日（The Byte Day）。然而，种种迹象表明，今年的庆祝活动将不仅仅是一场乡村家庭聚会。

拜特镇的居民在一个关键问题上产生了严重分歧。有些人认为，按照传统，一个字节应该始终等于 8 位。然而，进步派支持者更倾向于容量更大的 16 位字节。另一些人则以更死板的态度看待整个问题，热切地希望宣布字节应该始终只有 4 位。最后，拜特镇还有一些不太重要的颠覆性运动，其成员主张字节中的位数不应该是 2 的幂，甚至不一定非得是偶数！所有这些团体都计划举行自己的示威游行，以说服拜特镇的居民支持他们的主张。

许多拜特镇居民担心，如此多的示威活动可能会干扰字节日的庆祝活动。拜特镇的市长察觉到，通过禁止部分示威活动可以获得巨大的公众支持。由于此类决定会引发争议，市长决定最多只取消两场示威活动。此外，他希望能够选择取消哪些示威活动，使得在取消后，剩余所有可能进行的示威活动所占用的总时间尽可能短。请帮助市长，告诉他他能实现的没有示威活动的时间总长是多少。

输入格式

第一行包含一个整数 $n$ ($2 \leqslant n \leqslant 500\,000$)：计划中的示威活动数量。接下来的 $n$ 行，每行描述一场示威活动：第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($0 \leqslant a_i < b_i \leqslant 10^9$)，表示第 $i$ 场示威活动在日出后 $a_i$ 分钟开始，在日出后 $b_i$ 分钟结束。

输出格式

你的程序应输出一个非负整数，表示在市长最多取消两场示威活动的情况下，示威活动所占用的总时间最多能缩短多少。

样例

样例输入 1

5
0 9
1 4
2 5
7 9
6 7

样例输出 1

4

说明

样例说明：市长应该取消第一场和第四场示威活动的许可。