beecrowd | 3133

Ship Queue

By Carlos de Salles, UFMA BR Brazil

Timelimit: 1

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.


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).


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

Input Sample Output Sample

10 -1
10 -1
10 -1
10 -1


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


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