New Year's '17 P6 - Christmas Cards

View as PDF
Submit solution
Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M
Authors:
imaxblue, r3mark
Problem type

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 ci and draw di 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≤N≤5000), the number of cards in his deck.
Next N lines: the ci and di values of the ith card of Firebat's deck (from top to bottom). (0≤ci,di≤109).

Output Specification

A single integer, the minimum mana he must spend to draw his entire deck.

Sample Input

Copy
8
20 3
5 0
13 3
9 3
18 2
4 1
17 1
8 0

Sample Output

Copy
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


  • 21
    imaxblue  commented on Aug. 14, 2018, 5:08 p.m.

    I don't see why he doesn't just play Myra's Unstable Element


    • -10
      Natsuki  commented on Jan. 20, 2019, 6:09 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • 7
    Ken_Shi  commented on Jan. 2, 2017, 12:07 a.m.

    When my favorite game connects to contest, only sadness left...


  • 1
    alei  commented on Jan. 1, 2017, 4:28 p.m.

    is possible to play the same card multiple times?


    • 1
      FatalEagle  commented on Jan. 1, 2017, 4:28 p.m.

      No, each card can only be played once.


  • 1
    grikukan  commented on Jan. 1, 2017, 2:36 p.m.

    What should I output if it's impossible to draw all cards?


    • 1
      imaxblue  commented on Jan. 1, 2017, 2:44 p.m.

      It is guaranteed to be possible. This has been updated in the problem statement. Sorry for any inconvenience.