No.37 遊園地のアトラクション
yuki2006問題文
Raymondは、遊園地に遊びに来ている。
遊園地の滞在時間は\(T\)時間で、各アトラクションの満足度が
\(i\)番目のアトラクションに乗ったら、満足度\(V_i\)が得られる。
しかし、遊園地は、どのアトラクションも行列であり、なかなか乗ることが出来ない。
\(i\)番目のアトラクションの行列は、\(c_i\)時間並ぶことでアトラクションに乗れるとする。
(アトラクション自体の時間は行列の時間に含まれているとする）
しかし、Raymondは同じアトラクションにはあまり乗りたくない。
滞在時間中に同じアトラクションに乗った場合は、
満足度は「\(V_i\)の半分小数切り捨て」しか得られず、その値を新たな\(V_i\)とする。
それ以降、また同じアトラクションに乗るたびに半減していく。
滞在時間の
\(T\)時間の間に得られる最大の満足度を得たいとするとき、
その得られる満足度を求めてください。
入力
\(T\) \(N\) \(c1 \, c2 \dots ci \dots cN\) \(v1 \, v2 \dots vi \dots vN\)
1行目に滞在時間を表す\(T (1 \le T \le 10000)\) が与えられます
2行目にアトラクションの数を表す\(N (1 \le N \le 15)\) が与えられます
3行目に各アトラクションの行列の時間を表す\(ci (1 \le ci \le 100,1 \le i \le N)\) が与えられます
4行目に各アトラクションの満足度を表す\(vi (1 \le vi \le 500,1 \le i \le N)\) が与えられます
出力
Raymondが得られる満足度の最大値を出力してください
最後に改行してください。
サンプル
サンプル1
入力
5 3 1 2 3 3 2 1
出力
6
アトラクション1(満足度3),アトラクション2(満足度2),アトラクション1(満足度1)を乗ることで最大の満足度を得られる。
サンプル2
入力
9 2 8 2 9 7
出力
11
アトラクション1は満足度が高いが、アトラクション2を乗り続けたほうが最終的な満足度は高くなる。
4回目以降は満足度は得られない。
満足度は7+3+1=11になる。1回乗るごとに半分切り捨てになるので注意。
サンプル3
入力
9 2 8 2 9 5
出力
9
この場合は、アトラクション1を1回乗るのが良い
サンプル4
入力
20 5 10 7 9 5 7 5 8 2 8 1
出力
20
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。