
fun main(args: Array<String>) {

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


    val m = Array(N + 1) { BooleanArray(W + 1) }
    val memo = Array(N + 1) { LongArray(W + 1) }
    fun resolve(index: Int, weight: Int): Long {

        if (m[index][weight]) {
            return memo[index][weight]
        }
        val result = when {
            index == N -> {
                0
            }
            weight < w[index] -> {
                resolve(index + 1, weight)
            }
            else -> {
                Math.max(
                    resolve(index + 1, weight - w[index]) + v[index],
                    resolve(index + 1, weight)
                )
            }
        }
        memo[index][weight] = result
        m[index][weight] = true
        return result
    }

    resolve(0, W).let(::println)
}
