fun main(args: Array<String>) {
    edpd()
}

data class Item(val weight: Int, val price: Int)

fun edpd() {
    val (n, w) = readLine()!!.split(" ").map { it.toInt() }
    val items = (1..n).map { readLine()!!.split(" ").map { it.toInt() } }
        .map { Item(it[0], it[1]) }

    val dp = Array(n) { LongArray(w + 1) { -1L } }

    val answer = dp(0, w, n, items, dp)

    println(answer)
}

fun dp(itemIndex: Int, remainWeight: Int, n: Int, items: List<Item>, dp: Array<LongArray>): Long {
    if (itemIndex == n) return 0

    if (dp[itemIndex][remainWeight] != -1L) {
        return dp[itemIndex][remainWeight]
    }

    val currentItem = items[itemIndex]

    val result = if (currentItem.weight > remainWeight) {
        dp(itemIndex + 1, remainWeight, n, items, dp)
    } else {
        Math.max(
            dp(itemIndex + 1, remainWeight, n, items, dp),
            currentItem.price
                    + dp(itemIndex + 1, remainWeight - currentItem.weight, n, items, dp)
        )
    }

    dp[itemIndex][remainWeight] = result

    return result
}
