## Christmas Cards

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Authors:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

For Christmas, Firebat received a new Hearthstone (a card game) expansion! In this game there is a deck of cards. Unfortunately for him, this expansion only contained draw cards. Each card has a mana cost and draw 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: , the number of cards in his deck.
Next lines: the and values of the card of Firebat's deck (from top to bottom). .

#### 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 mana.

• commented on Aug. 14, 2018, 1:08 p.m.

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

• commented on Jan. 20, 2019, 1:09 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on Jan. 1, 2017, 7:07 p.m.

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

• commented on Jan. 1, 2017, 11:28 a.m.

is possible to play the same card multiple times?

• commented on Jan. 1, 2017, 11:28 a.m.

No, each card can only be played once.

• commented on Jan. 1, 2017, 9:36 a.m.

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

• commented on Jan. 1, 2017, 9:44 a.m.

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