You have N items that you want to put them into a knapsack. Item i has value vi and weight wi.

You want to find a subset of items to put such that:

* The total value of the items is as large as possible.
* The items have combined weight at most W, that is capacity of the knapsack.



Find the maximum total value of items in the knapsack.

Constraints

* 1 ≤ N ≤ 100
* 1 ≤ vi ≤ 100
* 1 ≤ wi ≤ 10,000,000
* 1 ≤ W ≤ 1,000,000,000

Input


N W
v1 w1
v2 w2
:
vN wN


The first line consists of the integers N and W. In the following N lines, the value and weight of the i-th item are given.

Output

Print the maximum total values of the items in a line.

Examples

Input

4 5
4 2
5 2
2 1
8 3


Output

13


Input

2 20
5 9
4 10


Output

9

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
#define down_queue(x) priority_queue<x>
#define up_queue(x) priority_queue<x, vector<x>, greater<x>>
#define vec(x) vector<x>
ll gcd(ll a,ll b){while(b){ll tmp = a % b;a = b;b = tmp;}return a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
#define rep(x, y) for(int x = 0; x < (y); x++)
#define REP(x, z, y) for(int x = (z); x < (y); x++)
#define all(x) x.begin(), x.end()
#define split_str(str, sp_word) istringstream stream(str); string res; for(int cnt = 0; getline(stream,res,sp_word); cnt++)
#define digit(x) ((int)log10((double)(x)) + 1)
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define out(x) for(auto i : x) cout << i << " "; cout << endl;
#define outln(x) for(auto i : x) cout << i << " " << endl;
#define vec_cpy(to,from) copy(all(to),back_inserter(from))
#define ary_cpy(to,from) memcpy(to, from, sizeof from)
#define MOD = 1000000007; 
#ifdef DEBUG
#define debug_echo(e) cout << "L" << __LINE__ << ": " << e << endl
#define debug_var(e) cout << "L" << __LINE__ << ": " << #e << " = " << e << endl
#else
#define debug_echo(e)
#define debug_var(e)
#endif
#ifdef DEBUG
#define debug_echo_dp1(dp, N) { cout << "[ "; rep(i, N) cout << dp[i] << " ";  cout << "]" << endl; }
#else
#define debug_echo_dp1(dp, N)
#endif

#define MAX_N 100
#define MAX_W 1000000000

int N;
int W;
int v[MAX_N];
int w[MAX_N];

int dp[MAX_N+1][MAX_W+1];

int rec(int i, int curw){
  if (dp[i][curw] != -1) return dp[i][curw];
  int res;
  if (i == N) {
    res = 0;
  } else if (curw+w[i] > W)  {
    res = rec(i+1, curw);
  } else {
    res = max(rec(i+1, curw), rec(i+1, curw+w[i]) + v[i]);
  }
  return dp[i][curw] = res;
}

int main() {
  cin >> N >> W;
  rep(i, N) {
    cin >> v[i] >> w[i];
  }
  memset(dp, -1, sizeof(dp));

  cout << rec(0, 0) << endl;
  rep(i, N) {
    rep(j, W) {
      debug_echo(dp[i][j]);
    }
  }
}