fun main(args: Array<String>) {

    val (N, W) = readLine()!!.split(" ").map(String::toInt)
    val WV = Array(N) { readLine()!!.split(" ").map(String::toLong) }
    val w = WV.map { it[0].toInt() }
    val v = WV.map { it[1] }

    val dp = Array(N) { LongArray(W + 1) }


    for (j in w[0].toInt()..W) {
        dp[0][j] = v[0]
    }
    for (i in 1 until N) {
        for (j in 0..W) {
            dp[i][j] = when {
                w[i] > j -> {
                    dp[i - 1][j]
                }
                w[i] > W -> {
                    dp[i - 1][j]
                }
                else -> {
                    Math.max(
                        // 現状維持
                        dp[i - 1][j],
                        // 入れる
                        dp[i - 1][j - w[i]] + v[i]
                    )
                }
            }
        }
    }

    println(dp.last().last())
}
