Alice must go to school everyday, but she wants to make the journey interesting, so she would like to play a game this time.

There are n stones on the road, Alice go though these stones step by step. In each step, Alice could go to the next nearest stone. She will throw this stone ahead if the current number of step is odd, otherwise, she will skip it. Now, you have the information about the stones, i.e., each stone has two attributes: P_{i } (the position of that stone) and D_{i} (the throw distance of that stone), and you are asked to find the largest distance Alice could walk.

Please note that if there are two or more stones at the same position, Alice will go to the one with the smallest D_{i} first.