For Christmas, Firebat received a new Hearthstone (a card game) expansion! In this game, there is a deck of 
~N~ cards. Unfortunately for him, this expansion only contained draw cards. Each card has a mana cost 
~c_i~ and draw 
~d_i~ cards from the top of the deck. Still the optimist, Firebat created a deck out of only these draw cards. We all know Firebat is the ultimate hearthstone player, and thus, knows exactly the order of the cards in his deck, does not have a hand limit and can use more than 10 mana. Nevertheless, he would like to maximize value. He starts off the game with only the first card of his deck in his hand (it's only fair for his opponent). Help him by determining the minimum mana he needs to spend in order to draw his entire deck (and possible overdraw).
It will always be possible to draw all cards. Once Firebat plays a card, he cannot play it again.
Input Specification
First line: ~N~ 
~(1 \le N \le 5\,000)~, the number of cards in his deck.
Next ~N~ lines: the ~c_i~ and ~d_i~ values of the 
~i^{th}~ card of Firebat's deck (from top to bottom). 
~(0 \le c_i, d_i \le 10^9)~.
Output Specification
A single integer, the minimum mana he must spend to draw his entire deck.
Sample Input
8
20 3
5 0
13 3
9 3
18 2
4 1
17 1
8 0
Sample Output
33
Explanation
For the minimal cost, Firebat should play the first card, drawing the next three. He should then play the fourth card and then the sixth card, emptying the deck. This gives a total of 
~33~ mana.
Comments
I don't see why he doesn't just play Myra's Unstable Element
This comment is hidden due to too much negative feedback. Show it anyway.
When my favorite game connects to contest, only sadness left...
is possible to play the same card multiple times?
No, each card can only be played once.
What should I output if it's impossible to draw all cards?
It is guaranteed to be possible. This has been updated in the problem statement. Sorry for any inconvenience.