fun main(args: Array<String>) {
    val (N, W) = readIntegerList()
    val dp = Array(N + 1) { LongArray(W + 1) { 0L } }
    for (i in 0 until N) {
        val (w, v) = readIntegerList()
        for (j in 0..W) {
            if (0 <= j - w) {
                dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - w] + v)
            } else {
                dp[i + 1][j] = dp[i][j]
            }
        }
    }
    println(dp[N].max())
}

fun readInteger() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntegerList() = readStringList().map(String::toInt)
fun readLongList() = readStringList().map(String::toLong)
