题目描述

宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。

一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。小智想要收服其中的一些小精灵，收服每个野生小精灵需要消耗一定数量的精灵球，同时皮卡丘会受到固定的体力伤害。

规则说明：

1. 皮卡丘体力**≤0**时，狩猎结束，且导致体力≤0的小精灵无法被收服；
2. 精灵球用完时，狩猎结束；
3. 每个小精灵只有两种选择：收服（消耗对应精灵球+承受伤害）或离开（无消耗）。

小智的目标优先级：

1. 主要目标：收服尽可能多的野生小精灵；
2. 次要目标：收服数量相同时，让皮卡丘剩余体力最大（受到的总伤害最小）。

已知精灵球总数、皮卡丘初始体力、每个小精灵的收服消耗，请求出最优方案。

输入格式

第一行三个整数 N, M, K：

• N：小智拥有的精灵球总数
• M：皮卡丘的初始体力
• K：野生小精灵的总数

接下来 K 行，每行两个整数 x, y：

• x：收服该小精灵需要的精灵球数量
• y：收服该小精灵对皮卡丘造成的伤害

输出格式

一行两个整数 C, R：

• C：最多能收服的小精灵数量
• R：收服 C 个小精灵时，皮卡丘的最大剩余体力

输入输出样例

样例输入1

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

样例输出1

3 30

样例输入2

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

样例输出2

0 100

样例说明

• 样例1：最优选择收服3个小精灵，总伤害70，剩余体力 100-70=30；
• 样例2：所有小精灵都无法安全收服，因此收服数量为0，剩余体力100。

数据范围

常规题目范围：$1 \le N,M \le 1000$，$1 \le K \le 100$