题目描述

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

规则说明：

1. 皮卡丘体力降至 0 或以下时，狩猎结束，且会导致体力 $\le 0$ 的小精灵无法被收服；
2. 精灵球用尽时，狩猎结束；
3. 对于每只小精灵，小智可以选择收服（消耗相应数量的精灵球，并使皮卡丘受到对应伤害）或离开（无消耗）。

小智的目标优先级为：

• 主要目标：收服尽可能多的野生小精灵；
• 次要目标：在收服数量最多的前提下，让皮卡丘剩余体力尽可能大（即受到的总伤害尽可能小）。

已知精灵球总数、皮卡丘的初始体力以及每只小精灵的收服消耗，请计算最优方案。

输入格式

第一行包含三个整数 $N, M, K$，分别表示小智拥有的精灵球总数、皮卡丘的初始体力值、野生小精灵的总数。

接下来 $K$ 行，每行包含两个整数 $x_i, y_i$，表示收服第 $i$ 只小精灵需要的精灵球数量和对皮卡丘造成的体力伤害值。

输出格式

一行两个整数 $C, R$，其中 $C$ 表示最多能收服的小精灵数量，$R$ 表示收服 $C$ 只小精灵时皮卡丘的最大剩余体力。

样例

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

3 30

提示

最优方案为收服 $3$ 只小精灵，总消耗精灵球数不超过 $10$，总伤害为 $70$。此时皮卡丘剩余体力 $100 - 70 = 30$。无法收服更多小精灵。

数据范围

• $1 \le N, M \le 1000$
• $1 \le K \le 100$
• $1 \le x_i \le N$，$1 \le y_i \le M$
• 精灵球与体力均为整数