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

fun p36() {
    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)
    }

    // [choose from (0..it) items][weight sum is lower than it]
    val dp = Array(n + 1) { IntArray(w + 1) }

    for ((index, item) in items.withIndex()) {
        for (wi in 0..w) {
            val (value, weight) = item

            // not choose item
            dp[index + 1][wi] = Math.max(dp[index + 1][wi], dp[index][wi])

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

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

    println(answer)
}

