fun main(args: Array<String>) {
    val (N, W) = readLine()!!.split(" "). map { it.toInt() }
    var dp = LongArray(W+1)
    for (i in 0 until N) {
        val dp2 = dp.clone()
        val (w,v) = readLine()!!.split(" "). map { it.toInt() }
        for (j in 0 .. W) {
            if ((j == 0 || dp[j] != 0L) && j+w<=W) {
                dp2[j+w] = Math.max(dp[j+w], dp[j] + v)
            }
        }
        dp = dp2
    }
    println(dp.max())
}