using namespace std;
using ll = long long;
const int NMAX = 1e2 + 11;
const int VMAX = 1e3 + 11;
int n, c, v_max, w[NMAX], v[NMAX];
ll mem[NMAX][VMAX];
ll solve(void)
{
    v_max = accumulate(v + 1, v + n + 1, 0);
    vector<vector<ll>> mem(n + 1, vector<ll>(v_max + 1, (ll)1e12));
    for (int i = 0; i <= n; ++i)
        mem[i][0] = 0;
    for (int i = 1; i <= n; ++i)
    {
        for (int vacc = 1; vacc <= v_max; ++vacc)
        {
            ll &ans = mem[i][vacc];
            if (vacc - v[i] >= 0)
                ans = min(w[i] + mem[i - 1][vacc - v[i]], mem[i - 1][vacc]);
            else
                ans = mem[i - 1][vacc];
        }
    }
    int ans = 0;
    for (int vacc = 1; vacc <= v_max; ++vacc)
        if (mem[n][vacc] <= c)
            ans = vacc;
    return ans;
}
int main(void)
{
    cin >> n >> c;
    for (int i = 1; i <= n; ++i)
        cin >> w[i] >> v[i];
    cout << solve() << endl;
    return 0;
}

using namespace std;
using ll = long long;
const int NMAX = 1e2 + 11;
const int WMAX = 1e5 + 11;
int n, c, w[NMAX], v[NMAX];
ll mem[NMAX][WMAX];
bool vis[NMAX][WMAX];
ll dp(int i, int cl)
{
    ll &ans = mem[i][cl];
    if (i == n)
        return 0;
    if (vis[i][cl])
        return mem[i][cl];
    vis[i][cl] = true;
    ans = 0;
    if (cl - w[i] >= 0)
        ans = dp(i + 1, cl - w[i]) + v[i];
    return (ans = max(ans, dp(i + 1, cl)));
}
int main(void)
{
    cin >> n >> c;
    for (int i = 0; i < n; ++i)
        cin >> w[i] >> v[i];
    cout << dp(0, c) << endl;
    return 0;
}

using namespace std;
const int NMAX = 1e5 + 11;
int n, abc[NMAX][3], mem[NMAX][3];
bool vis[NMAX][3];
int dp(int i, int p)
{
    int &ans = mem[i][p];
    if (i == n)
        return 0;
    if (vis[i][p])
        return mem[i][p];
    vis[i][p] = true;
    ans = INT_MIN;
    for (int j = 0; j < 3; ++j)
    {
        if (j == p)
            continue;
        ans = max(ans, dp(i + 1, j) + abc[i][j]);
    }
    return ans;
}
int main(void)
{
    cin >> n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < 3; ++j)
            cin >> abc[i][j];
    cout << dp(0, -1) << endl;
    return 0;
}

using namespace std;
const int NMAX = 1e5 + 11;
int n, k, h[NMAX], mem[NMAX];
bool vis[NMAX];
inline int dh(int i, int j) { return (int)abs(h[i] - h[j]); }
int dp(int i)
{
    int &ans = mem[i];
    if (i == n - 1)
        return 0;
    if (vis[i])
        return ans;
    vis[i] = true;
    ans = INT_MAX;
    for (int j = i + 1; j <= i + k; ++j)
        if (j < n)
            ans = min(ans, dp(j) + dh(i, j));
    return ans;
}
int main(void)
{
    cin >> n >> k;
    for (int i = 0; i < n; ++i)
        cin >> h[i];
    cout << dp(0) << endl;
    return 0;
}

using namespace std;
const int NMAX = 1e5 + 11;
int n, h[NMAX], mem[NMAX];
bool vis[NMAX];
inline int dh(int i, int j) { return (int)abs(h[i] - h[j]); }
int dp(int i)
{
    int &ans = mem[i];
    if (i == n - 1)
        return 0;
    if (vis[i])
        return ans;
    vis[i] = true;
    ans = dp(i + 1) + dh(i, i + 1);
    if (i + 2 < n)
        ans = min(ans, dp(i + 2) + dh(i, i + 2));
    return ans;
}
int main(void)
{
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> h[i];
    cout << dp(0) << 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);
}
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));
}
int solve(int n, string s)
{
    map<char, vi> pm = {
        {'A', vi(n, 0)}, {'T', vi(n, 0)}, {'C', vi(n, 0)}, {'G', vi(n, 0)}};
    string opts = "AGCT";
    for (int i = 0; i < n; ++i)
    {
        for (auto c : opts)
        {
            pm[c][i] += s[i] == c;
            if (i != 0)
                pm[c][i] += pm[c][i - 1];
        }
    }
    auto sum = [&pm](int l, int r, char c) {
        return pm[c][r] - (l > 0 ? pm[c][l - 1] : 0);
    };
    int ans = 0;
    for (int l = 0; l < n - 1; ++l)
    {
        for (int r = l + 1; r < n; ++r)
        {
            ans += (sum(l, r, 'A') == sum(l, r, 'T') and
                    sum(l, r, 'C') == sum(l, r, 'G'));
        }
    }
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    string s;
    cin >> n >> s;
    cout << solve(n, s) << 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);
}
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));
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int a, b;
    cin >> a >> b;
    int x = (a + b) / 2;
    int y = (a - b) / 2;
    cout << x << " " << y << 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);
}
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));
}
int const NMAX = 1e5 + 11;
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vi f0(NMAX, 0), f1(NMAX, 0), f2(NMAX, 0);
    for (int i = 0; i < n; ++i)
    {
        int ai;
        cin >> ai;
        if (i % 2 == 0)
            ++f0[ai];
        else
            ++f1[ai];
        ++f2[ai];
    }
    sort(f0.begin(), f0.end(), greater<int>());
    sort(f1.begin(), f1.end(), greater<int>());
    sort(f2.begin(), f2.end(), greater<int>());
    f0;
    if (f2[0] == f0[0] + f1[0])
        cout << n - max(f0[0] + f1[1], f0[1] + f1[0]) << endl;
    else
        cout << n - f0[0] - f1[0] << 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);
}
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));
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vi a(n);
    read_n(a.begin(), n);
    sort(a.begin(), a.end());
    int ai = a.back();
    int aj = *max_element(a.begin(), prev(a.end()), [ai](int x, int y) {
        return min(x, ai - x) < min(y, ai - y);
    });
    cout << ai << " " << aj << 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);
}
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));
}
int const NMAX = 2e5 + 11;
int n, m, d[NMAX], ans[NMAX], vis[NMAX];
vector<ii> g[NMAX];
ii edges[NMAX];
void dfs(int u)
{
    vis[u] = true;
    for (auto [v, w] : g[u])
    {
        if (vis[v])
            continue;
        ans[v] = ans[u] + w;
        dfs(v);
    }
}
bool solve(void)
{
    for (int u = 0; u < n; u++)
        if (not vis[u])
            dfs(u);
    for (int i = 0; i < m; i++)
    {
        auto [u, v] = edges[i];
        if (ans[v] - ans[u] != d[i])
            return false;
    }
    return true;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v >> d[i], u--, v--;
        edges[i] = {u, v};
        g[u].emplace_back(v, d[i]);
        g[v].emplace_back(u, -d[i]);
    }
    cout << (solve() ? "Yes" : "No") << endl;
    return 0;
}