fun main(args: Array<String>) {
    val (n, m) = readLine()!!.split(' ').map { it.toInt() }

    val dp = Array(m + 1) { 0L }

    for (i in 0 until n) {

        val (s1, s2) = readLine()!!.split(' ')
        val w = s1.toInt()
        val v = s2.toLong()

        for (tw in m downTo 0) {
            if (tw - w >= 0) {
                dp[tw] = Math.max(dp[tw], dp[tw - w] + v)
            }
        }
    }

    println(dp[m])
}
