9685번 - Demonstrations 다국어

This Sunday, The Byte Day will be celebrated in Bytetown, one of the most important annual Bytelandian celebrations. However, everything indicates that this year jubilation will not only be a rural family fete.

Well, Bytetown citizens are strongly divided concerning one crucial matter. Some believe that in line with tradition, the byte should always be equal to eight bits. However there are progress supporters who would rather go for more capacious, 16 bit bytes. Others see the whole matter much more rigidly and would eagerly like to declare that the byte should always have only four bits. Finally there are less significant subversive movements in Bytetown, whose members advocate that the count of bits in the byte should not be the power of two, or yet it must not necessarily be an even number! All of these societies plan to hold their own manifestation in order to convince Bytetown citizens to their cases.

Many Bytetown citizens are afraid that such a number of demonstrations might interfere with the The Byte Day celebrations. The Lord Mayor of Bytetown sensed a significant public support could be gained, by forbidding some of the demonstrations. Due to the fact that such decisions raise controversy, the Lord Mayor decided he would only cancel two demonstrations. Additionally he would like to be able to choose such demonstrations for cancellation, that would result in the the total time taken by any other possible demonstrations taking place in the city after the cancellation, to possibly be shortest. Help The Lord Mayor and give him a clue how much time in the city without a demonstration he can achieve.

The first input line contains one integer n (2 ≤ n ≤ 500,000): the number of planned demonstrations. Each of the subsequent n lines describes one demonstration: i-th of those lines contains two integers a_i and b_i (0 ≤ a_i < b_i ≤ 10⁹), which mean that i-th demonstration begins a_i byteminutes after sunrise and ends b_i byteminutes after sunrise.

Your program should produce exactly one non-negative integer, describing by how much time demonstrations taking place could possibly be shortened, in case The Lord Mayor of Bytetown cancels maximum two demonstrations.

Lord Mayor of Bytetown should not issue permits for the first and the fourth demonstration.