/// Swift5 -> Swift2.2
extension String {
    // split(separator:maxSplits:omittingEmptySubsequences:)
    func split(separator separator: Character) -> [String] {
        return self.characters.split(separator).map(String.init)
    }
}
extension Array {
    // init(repeating:count:)
    init(repeating: Element, count: Int) {
        self.init(count: count, repeatedValue: repeating)
    }
}
extension Array where Element: Comparable {
    // sorted()
    func sorted() -> [Element] {
        return self.sort( { $0 < $1 } )
    }
}
// stride(from:through:by:)
func stride(from start: Int, through end: Int, by stride: Int) -> StrideThrough<Int> {
    return start.stride(through: end, by: stride)
}
// stride(from:to:by)
func stride(from start: Int, to end: Int, by stride: Int) -> StrideTo<Int> {
    return start.stride(to: end, by: stride)
}
/// end

let input = readLine()!.split(separator: " ").map { Int($0)! }
let N = input[0]
let W = input[1]

typealias Knapsack = (weight: Int, value: Int)
var knapsacks = [Knapsack]()
knapsacks.append((0, 0))

for _ in 0 ..< N {
    let knapsack = readLine()!.split(separator: " ").map { Int($0)! }
    knapsacks.append((knapsack[0], knapsack[1]))
}

var dp = Array(repeating: Array(repeating: 0, count: W + 1), count: N + 1)

for i in 1 ... N {
    for j in 0 ... W {
        dp[i][j] = max(dp[i][j], dp[i - 1][j])

        guard j - knapsacks[i].weight >= 0 else { continue }
        dp[i][j] = max(
            dp[i][j],
            dp[i - 1][j - knapsacks[i].weight] + knapsacks[i].value
        )
    }
}

print(dp.last!.last!)
