import sequtils,strutils,algorithm,math,future,macros
template get*():string = stdin.readLine().strip()
template `max=`*(x,y:typed):void = x = max(x,y)

let
  T = get().parseInt() # < 10000
  N = get().parseInt() # < 15
  C = get().split().map(parseInt) # < 100 # 残り時間
  V = get().split().map(parseInt) # < 500 # 満足度
# 二回目以降は v div 2
var dp = newSeqWith(N+1,newSeqWith(T+1,0)) # 残り時間 T
for i in 0..<N:
  var (cost,satis) = (C[i],V[i])
  var sumSatis = satis
  for t in 0..T: dp[i+1][t] = dp[i][t]
  while satis > 0:
    for t in cost..T:
      dp[i+1][t-cost] .max=  dp[i][t] + sumSatis
    satis = satis div 2
    cost += C[i]
    sumSatis += satis
echo dp[^1][0]