Time Limit: 3 Seconds
Memory Limit: 65536 KB
Diablo III is a very hot action role playing game in recent days.
There are n sections in the game, and our hero needs to clear these sections one by one (in order). In each section, there is only one elite monster or only one boss defending some treasures.
- Every time when the hero kills an elite monster, he will get a buff called "Nephalem Valor" which can increase the possibility of finding magic treasures. The buff can be accumulated and the upper limit is 5 level.
- Every time when the hero kills a boss with 5 level buff, the boss will definitely drop a legendary item. So in order to get legendary items, our hero will always choose to kill boss with 5 level buff, otherwise he will just skip the boss. If he kills a boss, all his buff will be reset to 0 level.
Besides, the battle with a boss is much more difficult than that with an elite monster. The hero may need to drink some life potions during a battle with a high level boss.
- Both our hero and the boss have hp full when the battle begins.
- To simplify the battle, we suppose that they will fight in turn. In every turn they will cast 1 spell on each other (the hero casts first, then the boss), and both the spells have their own damage value.
- When the hero or the boss's hp is no more than 0, the battle ends.
- Our hero has infinite life potions in his backpack. When he drinks a life potion, his hp will recover some points immediately (but his hp cannot be more than his initial full hp).
- He can drink the potion at any time, but he can only drink 1 potion during 1 turn.
Of course, when he has 5 level buff, he can also choose to skip the boss, since some boss may cost too many potions. The battle with elite monster dose not cost any life potion.
Now given the information our hero and the n sections, please find out how many legendary items our hero can get after clearing n sections. If there are multiple ways, choose the one which will cost minimum number of potions.
The input contains multiple test cases.
In each test case, first there is an integer n ( 1 <= n <= 50000 ) which is number of sections in the game.
Then there are n lines describing the sections one by one. In each line, the first integer indicates the type of the section ( 0 means elite monster, 1 means boss ). If it is a boss, then there are another 2 integers h ( 1 <= h <= 1000 ) and d ( 1 <= d <= 10 ) indicating the boss's hp and damage.
Finally, there is a line containing three integer, H ( 1 <= H <= 1000 ) indicating the hero's initial full hp, D ( 1 <= D <= 1000 ) indicating the hero's damage, P ( 1 <= P <= 1000 ) indicating the potion's recovering points.
For each test case, output 2 integers separated by a space.
The first integer is the maximum number of legendary items and the second integer is the minimum number of life potions to cost.
1 10 10
1 100 10
10 10 100
Author: HUANG, Qiao
Contest: ZOJ Monthly, June 2013