import Foundation

func readWords<T>(_ f: (Substring) -> T) -> [T] {
    return readLine()!.split(separator: " ").map(f)
}

func main() {
    let nw = readWords { Int($0)! }
    let n = nw[0]
    let w = nw[1]

    let items: [(w: Int, v: Int)] = (1...n).map { _ in 
        let wv = readWords { Int($0)! }
        return (w: wv[0], v: wv[1])    
    }
    var dp: [[Int]] = (0...n).map {_ in [Int](repeating: 0, count: w+1) }

    for i in 0..<n {
        for weight in 0...w {
            if items[i].w <= weight {
                dp[i+1][weight] = max(dp[i][weight-items[i].w] + items[i].v, dp[i][weight])
            } else {
                dp[i+1][weight] = dp[i][weight]
            }
        }
    }

    print(dp[n][w])
}


main()