fun main(args: Array<String>) {
    val (n, w) = readLine()!!.split(' ').map(String::toInt)
    val wList = mutableListOf<Int>()
    val vList = mutableListOf<Long>()
    (1..n).forEach {
        val (w, v) = readLine()!!.split(' ').map(String::toLong)
        wList.add(w.toInt())
        vList.add(v)
    }
    val dp = Array(n + 1) { LongArray(w + 1) { 0L } }
    for (i in 0 until n) {
        for (sum_w in 0..w) {
            if (sum_w - wList[i] >= 0) {
                if (dp[i + 1][sum_w] < dp[i][sum_w - wList[i]] + vList[i]) {
                    dp[i + 1][sum_w] = dp[i][sum_w - wList[i]] + vList[i]
                }
            }
            if (dp[i + 1][sum_w] < dp[i][sum_w]) {
                dp[i + 1][sum_w] = dp[i][sum_w]
            }
        }
    }
    println(dp.maxBy { it.max()!! }!!.max())
}