No.107 モンスター
nmnmnmnmnmnmnm問題文
$N$匹のモンスターがいる。
モンスターには$2$種類ある。
悪いモンスターと良いモンスターの$2$種類である。
悪いモンスターとは$1$匹に対し$1$回戦わないといけない。
戦うと体力が減りレベルが$1$上がる。
レベルが1上がると最大体力が$100$上がる。
もし体力が減って$0$以下になればそこで終了する。
良いモンスターは$1$匹につき$1$回だけ体力を回復してくれる。
ただし、回復する体力は最大体力を越えることはない。
自分の最初の体力は$100$で最大体力も$100$である。
悪いモンスターをすべて倒したい。
また、最後に残った体力をできるだけ多くしたい。
モンスターには自由な順番で出会える。
最後までどれだけの体力を残せるだろうか？
どのようにしても途中で体力が$0$以下になる場合は$0$を答えとする。
ただし、良いモンスターを倒すことは出来ない。
入力
$N$
$D_1\ D_2\ ... D_{N}$
$N$はモンスターの総数。$1\le N \le 16$。($N$は正の整数。)
$D_i$は$i$番目のモンスターの情報。
$D_i$が正の数であれば良いモンスターで|$D_i$|だけ回復してくれる。
$D_i$が負の数であれば悪いモンスターで倒すのに|$D_i$|だけ体力を使う。
$-1600 \le Di < 0、0 < Di \le 1600$。($D_i$は$0$以外の整数。)
出力
最後の時点での体力の最大値を1行で出力せよ。
どうがんばっても途中で体力が0以下になる場合には0を1行で出力せよ。
最後に改行を忘れずに。
サンプル
サンプル1
入力
3 -90 50 50
出力
110
最初に1番目の悪いモンスターと戦う。
体力が10になり、最大体力が200になる。
2,3番目の2匹の良いモンスターに体力を50ずつ回復してもらう。
最終的な体力は110になる。
もし、先に回復を行っても体力は最大体力の100より増えない。
この場合、最後に戦うと最終的な体力は10になる。
サンプル2
入力
4 -90 230 -120 120
出力
240
1番目の悪いモンスターと戦う。
体力は10、最大体力は200になる。
4番目の良いモンスターに回復してもらう。
体力は130になる。
3番目の悪いモンスターと戦う。
体力は10、最大体力は300になる。
2番目の良いモンスターに回復してもらう。
体力は240になる。
サンプル3
入力
4 -10 -300 100 100
出力
0
1番目の悪いモンスターと戦うと体力が90に減り最大体力は200になる。
3,4番目の良いモンスターに体力200まで回復してもらうことはできる。
しかし、どうがんばっても2番目の悪いモンスターと戦うと体力は0以下になる。
サンプル4
入力
4 -40 -60 210 -110
出力
50
2番目の悪いモンスターと戦う。
体力は40、最大体力は200になる。
3番目の良いモンスターに回復してもらう。
最大体力を超えられないので体力は200になる。
1,4番目の悪いモンスターと戦う。
体力は50になる。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。