002 - ギギギ・・・ガガ・・・ゴゴゴゴ

時間制限 1 秒 / メモリ制限 64 MB / 得点 100 / x 7 /


TLE
1sec
MLE
64MB
得点
100
12/19 14:20 テストケースの不備によりリジャッジを行いました。

野生のレジギガスが現れた!!!

このポケモンの体力は $hp$、攻撃力は $INF$ である。
しかし、なんとこのポケモン、$t$ ターン動けない。かわいそう。
あなたのポケモンの体力は $h$ で、$n$ 個の技を持っている。
$i$ 個目の技は $a_i$ の威力で、一回のみ使える。
ただ倒せばいいだけなら苦労しないが、このポケモンは(受けたダメージの総和)−(体力 $(hp)$)のダメージをやられた時に放ってくる。
要するに、オーバーキルのしすぎは許されないのだ。
レジギガスを倒せた上で、あなたのポケモンが瀕死でない(体力が $1$ 以上)なら gigigi...、そうでないなら gagagagaga と出力せよ。改行を忘れないこと。

入力

$hp$ $t$
$h$ $n$
$a_1$ 
$\vdots$
$a_n$

制約

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

  • $0 \leq h,hp \leq 10^8$
  • $1 \leq t,n \leq 20$
  • $5 \leq a_i \leq 10^7$

入出力例

入力例1

100 3
100 5
5 
10 
20 
15 
90 

出力例1

gigigi...

解説

威力 $90,10$ の技を出せば、レジギガスを倒せた上に、こちらのダメージは $0$ で抑えることができる。

入力例2

500 5
150 7
5
10
15
20
5
30
50

出力例2

gagagagaga

解説

どう頑張っても無理である。

入力例3

100 3
10 5
200
300
400
500
600

出力例3

gagagagaga

解説

どの技を使ってもレジギガスを倒すことができるのだが、最低でも $100$ の反撃を受けるので、あなたのポケモンはやられてしまう。