fun main(args: Array<String>) {

    var (N,W) = readLine()!!.split(" ").map{it.toInt()}


    var dp = Array(N){LongArray(W+1){0}}
    var w = IntArray(N)
    var v = IntArray(N)

    for(i in 0 until N){
        val(wi,vi) = readLine()!!.split(" ").map{it.toInt()}
        w[i] = wi;
        v[i] = vi;
    }

    for(j in 0..W){
        if(w[0]  <= j){
            dp[0][j] = v[0].toLong()
        }
    }

    for(i in 1 until N){
        for(j in 0..W){
            if(w[i] > j) {
                dp[i][j] = dp[i-1][j]
            } else {
                dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-w[i]] + v[i])
            }
        }
    }

    println(dp[N-1][W])

}
