fun main(args: Array<String>) {

    val (N, W) = readLine()!!.split(" ").map(String::toInt)
    val WV = Array(N) { readLine()!!.split(" ").map(String::toInt) }
    val w = WV.map { it[0] }
    val v = WV.map { it[1] }

    val dp = LongArray(W + 1)

    for (i in 0 until N) {
        for (j in W downTo w[i]) {
            dp[j] = Math.max(dp[j - w[i]] + v[i], dp[j])
        }
    }
//    dp.joinToString(",").let(::println)

    println(dp.last())
}
