import kotlin.math.max

fun main() {
    val (n, limit) = readLine()!!.split(" ").map { it.toInt() }
    val items = mutableListOf<Item>()

    repeat(n) {
        val (w, v) = readLine()!!.split(" ").map { it.toInt() }
        items.add(Item(w, v))
    }

    val dp = LongArray(limit + 1) { 0 }

    items.forEach {
        for (j in limit - it.weight downTo 0) {
            dp[j + it.weight] = max(dp[j + it.weight], dp[j] + it.value)
        }
//        dp.forEach { print("$it ") }
//        println()
//        println("-----------------------------------------")
    }
//    dp.forEach { print("$it ") }
//    println()

    println(dp.max())

}

private data class Item(
        var weight: Int = 0,
        var value: Int = 0
)