fun main(args : Array<String>) {
    val (n, w) = readLine()!!.split(" ").map { it.toInt() }
    val ww = mutableListOf<Int>()
    val vv = mutableListOf<Int>()

    repeat(n) {
        val (w1, v1) = readLine()!!.split(" ").map { it.toInt() }
        ww.add(w1)
        vv.add(v1)
    }

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

    for (i in 1..n) {
        for (j in 1..w) {
            if (j >= ww[i-1]) {
                dp[i][j] = Math.max(dp[i-1][j-ww[i-1]] + vv[i-1], dp[i-1][j])
            } else {
                dp[i][j] = dp[i-1][j]
            }
        }
    }

    println(dp[n][w])
}