题目描述

小智有N个精灵球，皮卡丘初始体力为M，面前有K只野生小精灵。收服第i只小精灵需要消耗一定数量的精灵球，并使皮卡丘受到一定伤害。每只最多收服一次，也可以选择放弃。

精灵球可以恰好用完，但皮卡丘的剩余体力必须大于0；使体力降到0或以下的那只小精灵不能被收服。

首先要使收服数量最多；在数量最多的前提下，使剩余体力最大。

输入格式

第一行三个整数N、M、K。接下来K行，每行两个整数，分别表示需要的精灵球数量和造成的伤害。

输出格式

输出两个整数，分别表示最多收服的数量和在此数量下最多剩余的体力。

样例

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

3 30

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

0 100

数据范围

1≤N<1000，1≤M<500，1≤K<100；每只所需精灵球为1至1000，造成的伤害为0至1000。