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.


#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp
n, w = map(int,input().split())
value = []
weight = []

for i in range(n):
    val,wei = map(int,input().split())
    value.append(val)
    weight.append(wei)
    

dp = []
for i in range(110):
    o = [0 for i in range(1010)]
    dp.append(o)



for ww in range(w):
    dp[0][ww] = 0

for i in range(n):
    for ww in range(w):
        
        if ww >= weight[i] :
            dp[i+1][w] = max(dp[i][w-weight[i]] + value[i], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
print(dp[n][w])



#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp
n, w = map(int,input().split())
value = []
weight = []

for i in range(n):
    val,wei = map(int,input().split())
    value.append(val)
    weight.append(wei)
    

dp = []
for i in range(110):
    o = [0 for i in range(10010)]
    dp.append(o)



for ww in range(w):
    dp[0][ww] = 0

for i in range(0,n):
    for ww in range(w+1):
        
        if ww >= weight[i] :
            dp[i+1][ww] = max(dp[i][ww-weight[i]] + value[i], dp[i][ww])
        else:
            dp[i+1][ww] = dp[i][ww]
print(dp[n][w])
