問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 187
作問者 : yuki2006yuki2006
6 ProblemId : 63 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:49:30

問題文

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もしくは右上の雲マークをクリックしてアカウントを作成してください。