#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  int t,n;
  cin>>t>>n;
  vector<int> c(n),v(n);
  for(int i=0;i<n;i++) cin>>c[i];
  for(int i=0;i<n;i++) cin>>v[i];

  vector<int> dp(t+1,0);
  for(int i=0;i<n;i++)
    for(int k=v[i];k;k>>=1)
      for(int j=t-c[i];j>=0;j--)
        chmax(dp[j+c[i]],dp[j]+k);

  cout<<*max_element(dp.begin(),dp.end())<<endl;
  return 0;
}