No.37 遊園地のアトラクション

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 118
作問者 : yuki2006yuki2006
3 ProblemId : 63 / 出題時の順位表

問題文

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
提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。