
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)

    val n = sc.nextInt()
    val w = sc.nextInt()

    val dp = Array(n + 1) { LongArray(w + 1) }
    val weights = IntArray(n)
    val values = IntArray(n)


    for (i in 0 until n) {
        weights[i] = sc.nextInt()
        values[i] = sc.nextInt()
    }

    for (i in 0 until n) {
        for (j in 1..w) {
            dp[i + 1][j] =
                if (j - weights[i] >= 0) Math.max(dp[i][j], dp[i][j - weights[i]] + values[i])
                else dp[i][j]
        }
    }

    println(dp[n][w])
}