/**
 * ナップザック問題
 * @link http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp
 */
fun main(args: Array<String>) {
    Main.init()

    Main.execute()

    Main.display()
}

class Main {
    companion object {

        private val DEFAULT_VALUE = 0

        private val matrix = arrayListOf<IntArray>()

        private var maxWeight: Int = 0
        private var itemNum: Int = 0


        private lateinit var itemList: List<Item>

        fun init() {
            val (inputItemNum, inputMaxWeight) = readLine()!!.split(" ")
            itemNum = inputItemNum.toInt()
            maxWeight = inputMaxWeight.toInt()

            itemList = List(itemNum) {
                val (value, weight) = readLine()!!.split(" ")
                Item(weight = weight.toInt(), value = value.toInt())
            }

            // matrixを準備
            for (index in 1..itemNum) {
                matrix.add(this.getEmptyMatrixRow())
            }
        }

        private fun getEmptyMatrixRow(): IntArray {
            return IntArray(maxWeight + 1) {
                DEFAULT_VALUE
            }
        }


        fun execute() {
            /**
             * matrixを走査
             */
            var round = 0
            while (itemList.lastIndex >= round) {
                val item = itemList[round]

                val currentRound = matrix[round]
                val previewRound =
                    if (round == 0) this.getEmptyMatrixRow() else matrix[round - 1]


                for (weight in 0 until currentRound.size) {

                    val valueWhenNone = previewRound[weight]

                    if (weight - item.weight < 0) {
                        currentRound[weight] = valueWhenNone
                        continue
                    }

                    val valueWhenAdded = previewRound[weight - item.weight] + item.value

                    if (valueWhenAdded > valueWhenNone) {
                        currentRound[weight] = valueWhenAdded
                    } else {
                        currentRound[weight] = valueWhenNone
                    }
                }
                round++
            }
        }

        fun display() {
            // 最大の値を出力
            println(matrix.last().max())
        }
    }
}

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