DMOPC '16 Contest 3 P3 - Phantom Fight

View as PDF
Submit solution
Points: 10 (partial)
Time limit: 0.6s
Java 8 1.0s
Python 2.5s
Memory limit: 64M
Python 128M
Authors:
Phoenix1369, jackyliao123
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 M 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 N enemy ghosts which will spawn one at a time, in the order they appear in the input.

The player can defeat the i^\text{th} (1 \le i \le N) ghost by drawing s_i symbols. If the i^\text{th} ghost is defeated, the player will be awarded with m_i 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 N and M, 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 N lines of input will contain two space-separated integers s_i and m_i (m_i, s_i \ge 0), denoting the number of symbols required to be drawn to defeat the i^\text{th} ghost, and the amount of magic the player will be awarded upon defeating this ghost, respectively.

Constraints

Subtask 1 [30%]

1 \le N \le 20

0 \le M \le 60

Subtask 2 [20%]

1 \le N \le 100

0 \le M \le 10^4

Subtask 3 [50%]

1 \le N \le 5000

0 \le M \le 10^4

It is guaranteed the net magic awarded after defeating a ghost (m_i - s_i) will never cause the player's magic to exceed 60 and 10^4 in subtasks 1 and both 2 and 3 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 4 ghosts, ignoring ghost #2 who rewards 0 magic. The amount of magic remaining after each victory resolves in order is 7, 5, 3, and 1.

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 0, and the maximum amount of magic he has remaining for defeating those 0 ghosts is the 3 units he possessed from the beginning.

Comments