001 - お菓子

問題

あるところにお菓子LOVEのもりぞーくんがいる。
彼ははお小遣いを貰ったら全額お菓子に使う。そこで考えた、

「お小遣いで、できるだけ多くの種類でなおかつ多くの数のお菓子を食べたい！」

そんなもりぞーくんのためにお小遣いで購入できる最適なお菓子の数を求めるプログラムを作ってあげよう。

入力

x n

s0 m0
s1 m1
  .
  .
sn-1 mn-1

１行目　お小遣いの額ｘ、お菓子の種類nが与えられる(整数 整数　半角区切り)
２行目　１種類目のお菓子の値段と個数(整数 整数　半角区切り)
３行目　２種類目のお菓子の値段と個数
.
.
n+1行目　n種類目のお菓子の値段と個数

出力

残りの残金と買えるお菓子の個数を半角区切りで出力

制約

全ての入出力ケースについて以下を満たす。

• 1 ≦ x ≦ 300000, 1 ≦ n ≦ 15, 100 ≦ s ≦ 100000, 1 ≦ m ≦　1000

---

入出力例

入力例1

500 5
10 30
3 60
100 5
20 6
30 6

出力例1

0 80

入力例2

300 3
12 444
24 21
5 20

出力例2

8 35

備考

・同額のお菓子はないものとする
・お菓子の個数より種類の多さを最優先とする