import java.util.*

fun main(args: Array<String>) {


    var sc = Scanner(System.`in`)


    val n = sc.nextInt()
    val w = sc.nextInt()

    var weights = IntArray(n + 1)
    var values = IntArray(n+1)

    for(i in 1..n){
        values[i] = sc.nextInt()
        weights[i] = sc.nextInt()
    }

    var dp = Array(n+1){LongArray(w + 1)}
    for(_w in 1..w){
        dp[0][_w] = 0
    }

    for(i in 1..n) {
        for (_w in 1..w) {
            if(_w - weights[i] < 0){
                dp[i][_w] = dp[i-1][_w]
            }
            else {
                dp[i][_w] = Math.max(dp[i - 1][_w], dp[i - 1][_w - weights[i]] + values[i])
            }
        }

    }
    println(dp[n][w])
}


