問題
あるところにお菓子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
備考
・同額のお菓子はないものとする
・お菓子の個数より種類の多さを最優先とする