406180: GYM102302 E Chi's performance

Chi is a little kid that goes to a middle school in London, Ontario. He is in a band, and they are planning on performing this weekend. There are $$$N$$$ members in this band, and each one is categorized by the id of the instrument that they play, represented by a number $$$V$$$, and their ability level represented by a number $$$P$$$.

The enjoyment of a performance depends on the order in which people play, and their ability levels. The playing order goes as follows: the order of people presenting has to be in the order of their instrument's id, from smallest to largest, and in case of ties any order of the people with the same instrument is valid. If two people in a row are playing the same instrument, the enjoyment level doesn't change. If two people in a row have different instruments, the enjoyment increases by the absolute diference of their ability levels, because people like to see very different kinds of performances even if the ability level decreases.

Chi wants to have the best performance ever, and he asked your help with this task. He wants to know what is the highest enjoyment of the performance, given an optimal ordering.

The first line will have an integer $$$N$$$ $$$(1 \leq N \leq 10^6)$$$. $$$N$$$ lines will follow. The $$$i$$$-th line will contain two integers $$$V_i$$$ $$$(1 \leq V_i \leq 10^9)$$$ and $$$P_i$$$ $$$(0 \leq P_i \leq 10^9)$$$ each, representing the $$$i$$$-th person's instrument id and ability level respectively.

Print a single number, representing the highest enjoyment possible of the performance, given an optimal ordering of the players.

6
3 10
1 5
1 8
4 3
3 12
4 1

16