## DMOPC '16 Contest 3 P3 - Phantom Fight

View as PDF

Points: 10 (partial)
Time limit: 0.6s
Java 8 1.0s
Python 2.5s
Memory limit: 64M
Python 128M

Authors:
Problem type

jackyliao123 is playing a new game he found online during math class. Because he is quite good at math, jackyliao123 tunes out the current math lecture and makes quick work of the final boss.

Disappointed by the underwhelming task, jackyliao123 draws up another game:

The player character begins with units of magic and consumes one unit of magic for every symbol drawn. Of course, if the player cannot consume a unit of magic (i.e. there is none remaining), the symbol will not be drawn.

There are enemy ghosts which will spawn one at a time, in the order they appear in the input.

The player can defeat the ghost by drawing symbols. If the ghost is defeated, the player will be awarded with units of magic. Otherwise, the ghost will simply cross over to the next life by vanishing instantly from the map.

As the end of the period draws near, jackyliao123 wants to determine the maximum possible number of ghosts which can be killed, and given this maximum, would also like to maximize the amount of magic remaining.

Can you write a program to help jackyliao123?

#### Input Specification

The first line of the input will contain two space-separated integers and , denoting the number of enemy ghosts to appear and the amount of magic the player has to start off in the game respectively.

The next lines of input will contain two space-separated integers and , denoting the number of symbols required to be drawn to defeat the ghost, and the amount of magic the player will be awarded upon defeating this ghost, respectively.

#### Constraints

It is guaranteed the net magic awarded after defeating a ghost will never cause the player's magic to exceed and in subtasks and both and respectively.

All numbers in the input will fit into a signed 32-bit integer.

#### Output Specification

Output two space-separated integers on a single line.

The first integer will denote the maximum possible number of ghosts the player can defeat if they play optimally.

The second integer will denote the maximum amount of magic remaining in the player's possession after defeating the maximum possible number of ghosts.

#### Sample Input 1

5 7
2 2
3 0
3 1
5 3
3 1

#### Sample Output 1

4 1

#### Explanation 1

The best possible score for jackyliao123 is to defeat ghosts, ignoring ghost # who rewards magic. The amount of magic remaining after each victory resolves in order is , , , and .

#### Sample Input 2

2 3
5 2
6 1

#### Sample Output 2

0 3

#### Explanation 2

jackyliao123 does not have enough magic to defeat either ghost spawned. Therefore, the maximum number of ghosts he can defeat is , and the maximum amount of magic he has remaining for defeating those ghosts is the units he possessed from the beginning.

• commented on Jan. 1, 2017, 8:11 p.m.

Is there any editorial available?

• commented on Dec. 13, 2016, 9:47 p.m.

Why do I get a WA return? Is it because of python?

• commented on Dec. 13, 2016, 11:42 p.m.

Yes, there is a custom checker for this problem that fails you if it detects python code.

• commented on March 24, 2019, 5:29 p.m. edit 2

Send python some love

• commented on Dec. 14, 2016, 12:43 a.m.

Noice