Public Class Program
  Shared Sub Main()
    Dim nw As Long() = Array.ConvertAll(Of String, Long)(Console.ReadLine().Split(" "), AddressOf Long.Parse)
    Dim n As Long = nw(0)
    Dim maxW As Long = nw(1)
    Dim dp(0 To n, 0 To 100000) As Long
    Dim weight(0 To n - 1) As Long
    Dim value(0 To n - 1) As Long
    For i As Long = 0 To n - 1
      Dim wv As Long() = Array.ConvertAll(Of String, Long)(Console.ReadLine().Split(" "), AddressOf Long.Parse)
      weight(i) = wv(0)
      value(i) = wv(1)
    Next
    For i As Long = 1 To n
      For j As Long = 0 To maxW
        dp(0, j) = 0
        If j >= weight(i - 1) Then
          dp(i, j) = Math.Max(value(i - 1), dp(i - 1, j - weight(i - 1)) + value(i - 1))
        End If
        dp(i, j) = Math.Max(dp(i - 1, j), dp(i, j))
      Next
    Next
    Console.WriteLine(dp(n, maxW).ToString())
  End Sub
End Class