問題
あなたは今からゲームで遊ぼうとしています。遊ぼうとしているゲームはN個で表され、ゲームiで遊ぶとTi分かかり満足度Siを得られます。ただし同じゲームは1度遊ぶと壊れてしまうため一回までしか遊べないものとします。ですが今からX分後に隕石が降ってくるらしいのでX分の間に得られる満足度の最大値を求めてください。 ただし、もし遊ぼうとしているゲームiが満足度が777だった場合、満足度777を得られ更にゲームから謎の光が出て隕石振って来るまでの時間が逆に$T_i$分伸びるものとします。その後このゲームは壊れてしまうためできなくなってしまうものとします。このときに隕石が降って来るまでの時間X分が$10^{4}$分を超えた場合はHappy！と出力してください。
入力
入力は以下の形式で標準入力から与えられる。
$X$ $N$ $T_1 S_1$ $T_2 S_2$ : : $T_N S_N$
1行目に隕石が降って来るまでの時間$X$分とあそぼうとしているゲームの個数$N$個が与えられる。
2行目以降にゲームiをする時間$T_i$分と得られる満足度$S_i$が与えられる。
出力
出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $1 \leq X \leq 10^{4}$
- $1 \leq N \leq 100$
- $1 \leq T_i \leq 10^{4}$
- $0 \leq S_i \leq 10^{8}$
- 入力はすべて整数で与えられる
入出力例
入力例1
10 5 2 10 3 3 5 20 7 2 4 12
出力例1
33
時間10分以内に得られる満足度の最大値は33になります。その後隕石が衝突してお亡くなりになります。
入力例2
10 4 2 10 4 50 25 100 10000 777
出力例2
Happy!
このときは得られる満足度が777のゲームがありますので消費する時間10000分が逆に隕石衝突まで伸びて合計10010分となり隕石衝突までの時間が$10^{4}$分より大きくなったためHappy!と出力します。
入力例3
10 4 1000 777 2000 777 3000 777 4000 777
出力例3
Happy!
このときは満足度777のゲームが4つありそれぞれ1000、2000、3000、4000分かかるので合計10000分隕石衝突までの時間が伸び結果的にHappy!と出力します。
ゲームってすごいね