bee 3133 - Ship Queue

Several ships are waiting on the coast to dock at the port. Each of these ships pays a rate when they dock, generating profit for the port. However, if the ship does not dock that day, the port must pay a fine for leaving that ship waiting. However, that the port can only serve, at most, three ships a day, earning the profit from these three ships and paying a fine to all the others who are waiting.

Your task is to inform the maximum profit or minimum loss (expressed by negative values) that a set of N ships (no more than 100) waiting to dock can generate that day. Realize that you need to maximize profit only on that day, considering that you can serve a maximum of 3 ships, and without worrying about the following days.

Input

The input consists of a first line containing an integer N, which can vary from 3 to 10000. The integer N represents the number of ships to dock. After that, there are N lines containing, each one with a pair of integer numbers. The first of these integers represents the profit of one of the N ships when unloading (an integer from 1 to 1000) and the second integer is the loss if that ship is not serviced that day (a negative integer ranging from -1 to -100).

Output

The output is a single line, representing the maximum profit or minimum loss that day.

Input Sample	Output Sample
4 10 -1 10 -1 10 -1 10 -1	29

5 34 -2 2 -80 14 -18 89 -2 22 -34	93

8 311 -12 516 -33 976 -22 548 -43 63 -37 278 -33 8 -15 112 -12	1931