fun main(args: Array<String>) = p35()

fun p35() {
    data class Item(val value: Int, val weight: Int)

    val (n, w) = readLine()!!.split(' ').map { it.toInt() }
    val items = Array(n) {
        val (value, weight) = readLine()!!.split(' ').map { it.toInt() }
        Item(value, weight)
    }

    val dp = Array(n) { IntArray(w + 1) }

    for ((index, item) in items.withIndex()) {
        for (weightLimit in 0..w) {
            // not choose item
            if (index != 0) dp[index][weightLimit] = Math.max(dp[index][weightLimit], dp[index - 1][weightLimit])

            // choose item
            val weightSum = weightLimit + item.weight
            if (weightSum <= w) {
                dp[index][weightSum] = if (index == 0) item.value else Math.max(
                    dp[index - 1][weightSum],
                    if (weightSum <= w) dp[index - 1][weightSum - item.weight] + item.value else 0
                )
            }
        }
    }

    val answer = dp.last().last()

    println(answer)
}

