using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
int main(void)
{
    int n, x;
    cin >> n >> x;
    vi h(n), s(n);
    for (auto &hi : h)
        cin >> hi;
    for (auto &si : s)
        cin >> si;
    vvi dp(n + 1, vi(x + 1, 0));
    for (int i = 1; i <= n; ++i)
    {
        for (int c = 1; c <= x; ++c)
        {
            dp[i][c] = dp[i - 1][c];
            if (c - h[i - 1] >= 0)
                dp[i][c] = max(dp[i][c], dp[i - 1][c - h[i - 1]] + s[i - 1]);
        }
    }
    cout << dp[n][x] << endl;
    return 0;
}

using namespace std;
const int NMAX = 1e5 + 11;
const int INF = 1e7;
int n, d1[NMAX], d2[NMAX];
void manacher(const string &s)
{
    for (int i = 0, l = 0, r = -1; i < n; ++i)
    {
        int j = l + r - i;
        int k = (i > r) ? 1 : min(d1[j], j - l + 1);
        while (0 <= i - k and i + k < n and s[i - k] == s[i + k])
            ++k;
        d1[i] = k--;
        if (i + k > r)
        {
            l = i - k;
            r = i + k;
        }
    }
    for (int i = 0, l = 0, r = -1; i < n; ++i)
    {
        int j = l + r - i;
        int k = (i > r) ? 0 : min(d2[j + 1], j - l + 1);
        while (0 <= i - k - 1 and i + k < n and s[i - k - 1] == s[i + k])
            ++k;
        d2[i] = k--;
        if (i + k > r)
        {
            l = i - k - 1;
            r = i + k;
        }
    }
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    int i1, i2, k1, k2, r1, r2, l1, l2, l;
    while (cin >> s)
    {
        memset(d1, 0, sizeof(d1));
        memset(d2, 0, sizeof(d2));
        n = s.size();
        manacher(s);
        i1 = i2 = n - 1;
        for (int i = n - 1; i >= 0; --i)
        {
            k1 = d1[i], k2 = d2[i];
            r1 = i + d1[i] - 1, r2 = i + d2[i] - 1;
            if (r1 == n - 1 and k1 > d1[i1])
                i1 = i;
            if (r2 == n - 1 and k2 > d2[i2])
                i2 = i;
        }
        l1 = i1 - (d1[i1] - 1);
        l2 = i2 - d2[i2];
        l = min(l1, (d2[i2] > 0 ? l2 : INF));
        if (l == 0)
        {
            cout << s << endl;
        }
        else
        {
            cout << s;
            for (int i = l - 1; i >= 0; --i)
                cout << s[i];
            cout << endl;
        }
    }
    return 0;
}

using namespace std;
using ll = long long;
ll qn;
ll trial_division(ll n)
{
    ll count = 0;
    ll max_prime = -1;
    for (ll d = 2; d * d <= n; d++)
    {
        if (n % d == 0)
            ++count;
        while (n % d == 0)
        {
            n /= d;
            max_prime = max(max_prime, d);
        }
    }
    if (n > 1 and n != qn)
    {
        max_prime = max(max_prime, n);
        ++count;
    }
    if (count >= 2)
        return max_prime;
    return -1;
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    while (cin >> qn and qn)
    {
        cout << trial_division(abs(qn)) << endl;
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
vi prefix_function(string s)
{
    int n = (int)s.length();
    vi pi(n);
    for (int i = 1; i < n; i++)
    {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(NULL);
    int t, n, ix, maxp;
    string s;
    cin >> t;
    while (t--)
    {
        cin >> s;
        n = s.size();
        auto pi = prefix_function(s);
        ix = maxp = 0;
        for (int i = 0; i < n; ++i)
        {
            if (pi[i] > maxp and 2 * pi[i] == i + 1)
            {
                ix = i;
                maxp = pi[i];
            }
        }
        string ans(ix + 1, ' ');
        for (int i = 0; i <= ix; ++i)
            ans[i] = s[i];
        for (int j = (n - ix - 1); j < n - ix + 8 - 1; ++j)
            cout << s[j % (ix + 1)];
        cout << "..." << endl;
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
int main(void)
{
    int n, x;
    vi dp;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> x;
        auto it = lower_bound(dp.begin(), dp.end(), x);
        if (it != dp.end())
            *it = x;
        else
            dp.push_back(x);
    }
    cout << dp.size() << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int const NMAX = 2e5 + 11;
int n, m;
vi g[NMAX];
ii edges[NMAX];
bool color[NMAX];
bool bfs(int src)
{
    queue<int> frontier;
    vector<bool> visited(n + 1, false);
    frontier.push(src);
    color[src] = 1;
    while (not frontier.empty())
    {
        auto u = frontier.front();
        frontier.pop();
        for (auto v : g[u])
        {
            if (not visited[v])
            {
                frontier.push(v);
                color[v] = !color[u];
                visited[v] = true;
            }
            else if (visited[v] and color[v] == color[u])
                return false;
        }
    }
    return true;
}
int main(void)
{
    cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        edges[i] = {u, v};
    }
    if (bfs(1))
    {
        cout << "YES" << endl;
        for (int i = 0; i < m; ++i)
        {
            auto [u, v] = edges[i];
            cout << color[u];
        }
        cout << endl;
    }
    else
        cout << "NO" << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
using mii = map<int, int>;
int main(void)
{
    int n;
    cin >> n;
    vi k(n);
    mii freq;
    for (auto &ki : k)
        cin >> ki;
    int ans = 0;
    for (int i = 0, j = 0; i < n; ++i)
    {
        while (j < n and freq[k[j]] == 0)
        {
            ++freq[k[j]];
            ++j;
        }
        ans = max(j - i, ans);
        freq[k[i]]--;
    }
    cout << ans << endl;
    return 0;
}

using namespace std;
using ll = long long;
struct Song {
  ll length;
  ll beauty;
  bool operator<(const Song &s) const { return (beauty < s.beauty); }
};
int n, k;
Song songs[300100];
ll max_pleasure(void) {
  ll ans = 0, cur = 0, len = 0;
  priority_queue<ll, vector<ll>, greater<ll>> pq;
  sort(songs, songs + n);
  for (int i = n - 1; i >= 0; --i) {
    len += songs[i].length;
    if (pq.size() == k) {
      len -= pq.top();
      pq.pop();
    }
    pq.push(songs[i].length);
    cur = len * songs[i].beauty;
    ans = max(ans, cur);
  }
  return ans;
}
int main(void) {
  cin >> n >> k;
  for (int i = 0; i < n; ++i) {
    cin >> songs[i].length;
    cin >> songs[i].beauty;
  }
  cout << max_pleasure() << endl;
  return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using iii = array<ll, 3>;
using vi = vector<ll>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
ll solve(int n, vector<iii> projects)
{
    sort(projects.begin(), projects.end());
    vi dp(n + 1, 0);
    for (int i = 1; i <= n; ++i)
    {
        auto [ei, si, di] = projects[i];
        dp[i] = dp[i - 1];
        auto it = lower_bound(projects.begin(), projects.end(), iii{si, 0, 0});
        if (it != projects.begin())
        {
            --it;
            int j = distance(projects.begin(), it);
            dp[i] = max(dp[i], dp[j] + di);
        }
    }
    return dp[n];
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vector<iii> projects(n + 1);
    projects[0] = {-1, -1, -1};
    for (int i = 1; i <= n; ++i)
        cin >> projects[i][1] >> projects[i][0] >> projects[i][2];
    cout << solve(n, projects) << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
int const NMAX = 2e5 + 11;
int n, timer, val[NMAX], idval[NMAX], id[NMAX], sz[NMAX];
ll t[4 * NMAX];
vi g[NMAX];
void precompute(int u, int p)
{
    id[u] = timer++;
    sz[u] = 1;
    idval[id[u]] = val[u];
    for (auto v : g[u])
    {
        if (v == p)
            continue;
        precompute(v, u);
        sz[u] += sz[v];
    }
}
void build(int a[], int v, int tl, int tr)
{
    if (tl == tr)
        t[v] = a[tl];
    else
    {
        int tm = (tl + tr) / 2;
        build(a, v * 2, tl, tm);
        build(a, v * 2 + 1, tm + 1, tr);
        t[v] = t[v * 2] + t[v * 2 + 1];
    }
}
ll sum(int v, int tl, int tr, int l, int r)
{
    if (l > r)
        return 0;
    if (l == tl and r == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    return sum(v * 2, tl, tm, l, min(r, tm)) +
           sum(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
}
void update(int v, int tl, int tr, int pos, int new_val)
{
    if (tl == tr)
        t[v] = new_val;
    else
    {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v * 2, tl, tm, pos, new_val);
        else
            update(v * 2 + 1, tm + 1, tr, pos, new_val);
        t[v] = t[v * 2] + t[v * 2 + 1];
    }
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int q;
    cin >> n >> q;
    read_n(val, n);
    for (int i = 0; i < n - 1; ++i)
    {
        int u, v;
        cin >> u >> v, u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    precompute(0, 0);
    build(idval, 1, 0, n - 1);
    while (q--)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int u, x;
            cin >> u >> x, u--;
            update(1, 0, n - 1, id[u], x);
        }
        else
        {
            int u;
            cin >> u, u--;
            cout << sum(1, 0, n - 1, id[u], id[u] + sz[u] - 1) << endl;
        }
    }
    return 0;
}