Capturing Pokémon

Problem Background

Pokémon is a story about Ash and his partner Pikachu going on adventures together.

Problem Description

One day, Ash and Pikachu came to a Pokémon hunting ground, where there are many rare wild Pokémon. Ash wants to capture some of them. However, wild Pokémon are not so easy to catch. For each wild Pokémon, Ash may need to use many Poké Balls to capture it, and during the capture the wild Pokémon will also deal some damage to Pikachu (reducing Pikachu's stamina). When Pikachu's stamina drops to $0$ or below, Ash must end the hunt (because he needs to heal Pikachu), and the wild Pokémon that caused Pikachu's stamina to drop to $0$ or below will not be captured either. When Ash runs out of Poké Balls, the hunt also ends.

When Ash meets a wild Pokémon he has two choices: capture it, or leave it. If he chooses to capture, he will definitely throw the number of Poké Balls needed to capture that Pokémon, and Pikachu will definitely take the corresponding damage; if he chooses to leave, Ash loses no Poké Balls and Pikachu takes no damage.

Ash has two goals: his main goal is to capture as many wild Pokémon as possible; if the number that can be captured is the same, he wants Pikachu to take as little damage as possible (i.e. have as much remaining stamina as possible), because they still have to continue the adventure.

Given the number of Ash's Poké Balls, Pikachu's initial stamina, and for each wild Pokémon the number of Poké Balls needed to capture it and the damage it will deal to Pikachu during capture, determine how Ash should choose which Pokémon to capture to achieve his goal.

Input Format

The first line of input contains three integers: $N\ (0<N<1000)$, $M\ (0<M<500)$, $K\ (0<K<100)$, representing the number of Ash's Poké Balls, Pikachu's initial stamina, and the number of wild Pokémon, respectively.

The following $K$ lines each describe one wild Pokémon, containing two integers: the number of Poké Balls needed to capture it, and the damage it deals to Pikachu during capture.

Output Format

Output one line containing two integers: $C,R$, where $C$ is the maximum number of Pokémon that can be captured, and $R$ is the maximum remaining stamina of Pikachu when capturing $C$ Pokémon.

Sample Input 1

10 100 5
7 10
2 40
2 50
1 20
4 20

Sample Output 1

3 30

Sample Input 2

10 100 5
8 110
12 10
20 10
5 200
1 110

Sample Output 2

0 100

Hint

For sample input 1: Ash chooses $(7,10),(2,40),(1,20)$. He captures $3$ Pokémon in total, Pikachu takes $70$ damage, leaving $100-70=30$ stamina. So output 3 30.

For sample input 2: Ash cannot capture any Pokémon, and Pikachu takes no damage, so output 0 100.

Constraints

$0<N<1000$, $0<M<500$, $0<K<100$. Time limit 1s, memory limit 1024KiB for each test case.