問題文

Raymondは、遊園地に遊びに来ている。
遊園地の滞在時間は$T$時間で、各アトラクションの満足度が $i$番目のアトラクションに乗ったら、満足度$V_i$が得られる。

しかし、遊園地は、どのアトラクションも行列であり、なかなか乗ることが出来ない。
$i$番目のアトラクションの行列は、$c_i$時間並ぶことでアトラクションに乗れるとする。
(アトラクション自体の時間は行列の時間に含まれているとする）

しかし、Raymondは同じアトラクションにはあまり乗りたくない。
滞在時間中に同じアトラクションに乗った場合は、 満足度は「$V_i$の半分小数切り捨て」しか得られず、その値を新たな$V_i$とする。
それ以降、また同じアトラクションに乗るたびに半減していく。

滞在時間の $T$時間の間に得られる最大の満足度を得たいとするとき、 その得られる満足度を求めてください。

入力

$T$
$N$
$c1c2\dots ci\dots cN$
$v1v2\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が得られる満足度の最大値を出力してください
最後に改行してください。

サンプル

5
3
1 2 3
3 2 1

6

9
2
8 2
9 7

11

9
2
8 2
9 5

9

20
5
10 7 9 5 7
5 8 2 8 1

20