fun main(args: Array<String>) {
    edpd()
}

fun edpd() {
    val (n, weightLimit) = readLine()!!.split(" ").map { it.toInt() }
    val items = (1..n).map { readLine()!!.split(" ").map { it.toInt() } }
        .map { Item(it[0], it[1]) }

    val dp = Array(n + 1) { LongArray(weightLimit + 1) }

    for (i in items.indices) {
        val (weight, price) = items[i]
        for (wl in 0..weightLimit) {
            dp[i + 1][wl] = Math.max(dp[i + 1][wl], dp[i][wl])
            if (wl + weight <= weightLimit) {
                dp[i + 1][wl + weight] = Math.max(dp[i + 1][wl + weight], dp[i][wl] + price)
            }
        }
    }

    val answer = dp[n][weightLimit]

    println(answer)
}

data class Item(val weight: Int, val price: Int)
