#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int memo[10010][500];
int func(int t, int k, vector<int>& v, vector<int>& c)
{
    int& res=memo[t][k];
    if (res) return res;
    res=0;
    for(int i=k;i<v.size();++i) if (t>=c[i])
        res=max(res, func(t-c[i], i+1, v, c)+v[i]);
    return res;
}

int main()
{
    int t, n;
    while (cin>>t>>n) {
        vector<int> c(n), v(n);
        for(int& x: c) cin>>x;
        for(int& x: v) cin>>x;
        for(int i=0;i<n;++i) {
            int x=v[i], y=c[i];
            while (x/=2) { v.push_back(x); c.push_back(y); }
        }
        memset(memo, 0, sizeof(memo));
        cout<<func(t, 0, v, c)<<endl;
    }
}