#include<iostream> using namespace std; int T, N; int c[10001], v[10001]; int memo[16][10001]; /* int calc(int v, int n){ int ret=0; for(int i=0; i<n; i++){ ret+=v; v/=2; } return ret; } */ int rec(int i, int j){ if(memo[i][j]!=-1) return memo[i][j]; int ret=0; if(i==N){ ret=0; }else{ int n=j/c[i]; int V=v[i]; int s=0; for(int k=0; k<=n; k++){ if(k==0){ ret=rec(i+1, j); }else{ ret=max(ret, rec(i+1, j-c[i]*k)+s);//calc(v[i], k)); } s+=V; V/=2; } } return memo[i][j]=ret; } int main(){ cin>> T>> N; for(int i=0; i<N; i++) cin>> c[i]; for(int i=0; i<N; i++) cin>> v[i]; fill((int*)memo, (int*)memo+16*10001, -1); cout<< rec(0, T)<< endl; return 0; }