#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<algorithm>
#include<iostream>
#include<hash_map>
#include<iterator>
#include<iomanip>
#include<numeric>
#include<cstring>
#include<vector>
#include<bitset>
#include<string>
#include<deque>
#include<stack>
#include<queue>
#include<array>
#include<cmath>
#include<list>
#include<map>
#include<set>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

#define ordered_set tree<ll, null_type,less_equal<ll>, \
rb_tree_tag,tree_order_statistics_node_update>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define inf INT32_MAX
#define linf INT64_MAX
#define pf push_front
#define pb push_back
#define ppb pop_back
#define ppf pop_front
#define ff first
#define ss second

ll fastPow(ll n, ll k/*,ll m*/) {
    if (k == 0)return 1;

    ll res = fastPow(n, k / 2/*,m*/)/*%m*/;

    res = (res * res)/*%m*/;

    if (k & 1)res = (res * n)/*%m*/;

    return res/*%m*/;
}

ll fastPow(ll n, ll k, ll m) {
    if (k == 0)return 1;

    ll res = fastPow(n, k / 2, m) % m;

    res = (res * res) % m;

    if (k & 1)res = (res * n) % m;

    return res % m;
}

ll calcMod(ll a, ll m) {
    return (a % m + m) % m;
}

ll Ceil(ll n, ll m) {
    return (n + m - 1) / m;
}

const ll mod = 1e9 + 7, N = 200000 + 5, M = 17 + 5;

ll n, m, ops[1005];
vector<ll> a, b;
vector<vector<ll>> dp;

void preCalc() {
    for (ll i = 1; i < 1005; ++i) {
        ll x = 1, op = 0;
        while (x != i) {
            vector<ll> divs;
            for (int j = 1; j * j <= x; ++j) {
                if (x % j == 0) {
                    divs.pb(j);
                    if ((x / j) != j) {
                        divs.pb(x / j);
                    }
                }
            }
            sort(divs.begin(), divs.end());
            ll f = i - x;
            ll pos = upper_bound(divs.begin(), divs.end(), f) - divs.begin() - 1;
            x += divs[pos];
            op++;
        }
        cout << op << "\n";
        ops[i] = op;
    }
}

ll rec(ll i, ll j) {
    if (i == n)return 0;
    ll &ret = dp[i][j];
    if (ret != -1)return ret;
    ret = rec(i + 1, j);
    if (ops[a[i]] <= j)ret = max(ret, b[i] + rec(i + 1, j - ops[a[i]]));
    return ret;
}

bool solve() {
    cin >> n >> m;
    a.clear(), b.clear();
    a.resize(n), b.resize(n);
    for (auto &i:a)cin >> i;
    for (auto &i:b)cin >> i;

    ll y = 0;
    for (int i = 0; i < n; ++i)y += ops[a[i]];

    if (m >= y) {
        ll sum = 0;
        for (int i = 0; i < n; ++i) {
            sum += b[i];
        }
        return cout << sum << "\n", 0;
    }
    dp.clear(), dp.resize(n + 5, vector<ll>(m + 5, -1));
    cout << rec(0, m) << "\n";
    return 1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    preCalc();
   // cin >> t;
    while (t--) {
        //solve();
    }
    return 0;
}