import java.util.*

class Scanner(`in`: java.io.InputStream) {
    private val reader = java.io.BufferedReader(java.io.InputStreamReader(`in`))
    private var tokenizer: StringTokenizer? = null

    fun next(): String {
        if (tokenizer?.hasMoreTokens() != true) {
            tokenizer = StringTokenizer(reader.readLine())
        }
        return tokenizer!!.nextToken()
    }

    fun nextLine(): String {
        return if (tokenizer?.hasMoreTokens() != true) {
            reader.readLine()
        } else tokenizer!!.nextToken("\n")
    }
}

fun main(args: Array<String>) {
    val pw = java.io.PrintWriter(System.out)
    Problem.solve(Scanner(System.`in`), pw)
    pw.flush()
}

////////////////////////////////////////////////////////////////////////

fun IntArray2D(i: Int, j: Int, defaultValue: () -> Int) = Array(i) { IntArray(j) { defaultValue() } }
fun LongArray2D(i: Int, j: Int) = Array(i) { LongArray(j) }

fun Array<LongArray>.updateMax(i: Int, j: Int, v: Long): Long {
    if (this[i][j] < v) this[i][j] = v
    return this[i][j]
}

////////////////////////////////////////////////////////////////////////

object Problem {
    fun solve(sc: Scanner, pw: java.io.PrintWriter) {
        val N = sc.next().toInt()
        val W = sc.next().toInt()
        val WV = IntArray2D(N, 2) { sc.next().toInt() }
        val dp = LongArray2D(N + 1, W + 1)
        for (i in 1..N) {
            val w = WV[i - 1][0]
            val v = WV[i - 1][1]
            for (j in 1..W) {
                dp.updateMax(i, j, dp[i - 1][j])
                if (j >= w) dp.updateMax(i, j, dp[i - 1][j - w] + v) // 入れる
            }
        }
        pw.println(dp[N][W])
    }
}
