import java.util.*
import java.math.*
import java.lang.Math.*

private val readString: ()->String = {readLine()!!}
private val readInt: ()->Int = { readLine()!!.toInt() }
private val readLong: ()->Long = { readLine()!!.toLong() }
private val readListInt: ()->List<Int> = { readLine()!!.split(' ').map(String::toInt) }
private val readListLong: ()->List<Long> = { readLine()!!.split(' ').map(String::toLong) }
private val errPrintln: (String)->Unit = { msg -> System.err.println(msg) }
private val MOD = 1e9.toLong()+7
private val INF = Int.MAX_VALUE/2
private val LINF = Long.MAX_VALUE/2


fun solveD(M: Int, W: List<Int>, V: List<Int>): Long {
    var res = 0
    val N = W.size
    val MMAX = 1e5.toInt()
    val dp = Array(N+1){LongArray(MMAX+1){0L}}
    // dp[i][j] := [0,i) の品物で重さ j 以下で取れる最大価値

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

    return dp[N][M]
}


fun main(args: Array<String>) {
    val (N, M) = readListInt()
    val W = IntArray(N){0}
    val V = IntArray(N){0}
    for (i in 0 until N) {
        val (w, v) = readListInt()
        W[i] = w; V[i] = v
    }

    val ans = solveD(M, W.toList(), V.toList())

    println(ans)
}
