Training Site
Sideways banner

Bad Dragon

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 128 megabytes
Time limit: 4.0 seconds

Update: Please assume that any skills cast must be in order, i.e. if you cast both skills i and j, skill i must be cast before skill j for all i < j.

You are the knight in shining armour ready to rescue your princess, but she is guarded by the big bad dragon who is very scary. So scary that you do not dare to face the dragon directly. Luckily, the wizard in your party is able to cast a spell to make the big bad dragon go to sleep for a certain amount of time. The big bad dragon is not scary when it's sleeping.

Given this knowledge, you have decided to plan ahead and make the best use of time that the dragon is asleep and maximize the amount of hit point damage you can deal to the dragon before it wakes up.

The wizard is able to sleep the dragon for T seconds. You have 100 mana initially and S skills at your disposal. Each skill costs m_i mana and takes t_i seconds to cast and deals h_i hit points of damage. Each skill can only be used once. In addition, depending on your mood of the day, you either regenerate 1 or 0 mana per second. However, your mana can never exceed the maximum capacity of 100.

The damage of a skill is dealt at the end of its cast duration and the mana is used at the start of a cast. For example, suppose you regenerate 1 mana per second and have a skill with 10 seconds of cast time. If you cast your skill as soon as the wizard sleeps the dragon, you will deal hit point damage at exactly 10 seconds after the wizard has cast their spell. You will also regenerate up to 10 mana in this time, but you must have had sufficient mana to have cast the skill initially.

You want to know, after T seconds, what is the maximum amount of hit points you can deal to the dragon.


  • The first line contains two integers 1<=T<=100, 1<=S<=100, R=0 or 1, which are respectively: the numbers of seconds your wizard can sleep the dragon, the number of skills you have available, and the mana regenerated per second depending on your mood.
  • The next S lines each contain three integers 0<=m_i<=100, 1<=t_i<=T, and 1<=h_i<=1000 which describes the mana cost, seconds to cast, and the amount of hit point damage skill i does.


Please output one integer on one line with its value being the maximum amount of hit points you can deal to the dragon after T seconds.

Keep in mind this question takes a while to be tested on the server. Don't waste time waiting for it to complete. Move to the next question.


  • Subtask 1 (25 points): Each skill costs exactly 33 mana and there is no regeneration
  • Subtask 2 (25 points): You have access to 20 and only 20 skills and there is no regeneration
  • Subtask 3 (25 points): your skills cost 0 mana
  • Subtask 4 (50 points): No additional limits

Note: You always start with 100 mana and as you are not the most energetic knight in the kingdom you do not have to be casting a skill for the entire duration that the dragon is asleep for. Given you optimise the number of hit points dealt you're free to take a break for as long as you want.

Sample 1 Explanation

You do not regenerate mana due to your poor mood this time, therefore we can only use the first and second skill to achieve optimal hit point damage
The first skill costs 25 mana, takes 50 seconds, and deals 100 hit points of damage
The second skill costs 70 mana, takes 50 seconds, and deals 88 hit points of damage
Combined we've used 95 mana, 100 seconds exactly, and dealt 188 hit points of damage

  • Sample Input 1

    100 3 0
    25 50 100
    70 50 88
    5 10 33

    Sample Output 1

  • Sample Input 2

    100 2 1
    100 50 77
    60 50 33

    Sample Output 2