import kotlin.math.max

fun main() {
    val (n, mw) = readLine()!!.split(' ').map { it.toInt() }
    val xs = (0 until n).map {
        val (w, v) = readLine()!!.split(' ').map { it.toInt() }
        w to v
    }

    val dp = Array(n + 1) { mutableMapOf<Int, Int>() }
    dp[0][0] = 0

    for (i in 0 until n) {
        val (wi, vi) = xs[i]
        for (w in dp[i].keys) {
            dp[i + 1][w] = max(dp[i][w]!!, dp[i + 1][w] ?: 0)
            if (w + wi > mw) continue
            dp[i + 1][w + wi] = max(dp[i][w]!! + vi, dp[i + 1][w + wi] ?: 0)
        }
    }

    println(dp[n].maxBy { it.value }!!.value)
}
