fun main(args: Array<String>) {
    val (N, W) = readLine()!!.split(" "). map { it.toInt() }
    val dp = LongArray(W+1)
    val w = IntArray(N+1)
    val v = IntArray(N+1)
    for ( i in 0 until N) {
        val a = readLine()!!.split(" "). map { it.toInt() }
        w[i] = a[0]
        v[i] = a[1]
    }
    for (i in 0 until N) {
        for (j in W downTo w[i]) {
            dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i])
        }
    }
    println(dp.max())
}