using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Threading.Tasks;
using System.Globalization;
namespace Atcoder
{
    class Program
    {

        static void Main(string[] args)
        {
            StreamScanner scan = new StreamScanner(System.Console.OpenStandardInput());
            int N = scan.Integer();
            int W = scan.Integer();
            int[] w = new int[N];
            int[] v = new int[N];
            for (int i = 0; i < N; i++)
            {
                w[i] = scan.Integer();
                v[i] = scan.Integer();
            }
            long[,] dp = new long[N + 1, W+1];
            long max = 0;
            for (int i = 0; i < N ; i++)
            {
                for (int k = 0; k < W + 1; k++)
                {
                    if (k + w[i] <= W)
                    {
                        dp[i + 1, k + w[i]] = Math.Max(dp[i + 1, k + w[i]], dp[i, k] + v[i]);
                        max = Math.Max(max, dp[i + 1, k + w[i]]);
                    }
                    dp[i + 1, k] = Math.Max(dp[i + 1, k], dp[i, k]);
                }
            }
            Console.WriteLine(max);
        }
        static int nibutan(int med,int[]a)//med以上が何個あるか
        {
            int mae = 0;
            int ato = a.Length;
            while (true)
            {
                if (ato - mae <= 1) {
                    return mae; }
                int mid = (mae + ato) / 2;
                if (a[mid] > med) { ato = mid; }
                if (a[mid] <= med) { mae = mid; }
            }
        }


        public static int h;
        public static int w;
        public static int BFS(int height, int width, char[,] map)
        {
            int[] dx = new int[] { -1, 0, 0, 1 };
            int[] dy = new int[] { 0, 1, -1, 0 };
            bool[,] visited = new bool[h, w];
            int[,] len = new int[h, w];
            var queue = new Queue<Tuple<int, int>>();
            queue.Enqueue(new Tuple<int, int>(height, width));
            int max = 0;
            visited[height, width] = true;

            while (queue.Count > 0)
            {
                var now = queue.Dequeue();
                for (int i = 0; i < 4; i++)
                {
                    int ny = now.Item1 + dy[i];
                    int nx = now.Item2 + dx[i];
                    if (ny >= h || ny < 0 || nx >= w || nx < 0)
                        continue;
                    if (visited[ny, nx] || map[ny, nx] == '#')
                        continue;
                    visited[ny, nx] = true;
                    len[ny, nx] = len[now.Item1, now.Item2] + 1;
                    max = Math.Max(max, len[ny, nx]);
                    queue.Enqueue(new Tuple<int, int>(ny, nx));
                }
            }
            return max;
        }
    }
    public class StreamScanner
    {
        public StreamScanner(Stream stream) { str = stream; }
        private readonly Stream str;
        private readonly byte[] buf = new byte[1024];
        private int len, ptr;
        public bool isEof = false;
        public bool IsEndOfStream { get { return isEof; } }
        private byte read()
        {
            if (isEof) throw new EndOfStreamException();
            if (ptr >= len)
            {
                ptr = 0;
                if ((len = str.Read(buf, 0, 1024)) <= 0)
                {
                    isEof = true;
                    return 0;
                }
            }
            return buf[ptr++];
        }
        public char Char()
        {
            byte b = 0;
            do b = read();
            while (b < 33 || 126 < b);
            return (char)b;
        }
        public string Scan()
        {
            var sb = new StringBuilder();
            for (var b = Char(); b >= 33 && b <= 126; b = (char)read())
                sb.Append(b);
            return sb.ToString();
        }
        public long Long()
        {
            long ret = 0; byte b = 0; var ng = false;
            do b = read();
            while (b != '-' && (b < '0' || '9' < b));
            if (b == '-') { ng = true; b = read(); }
            for (; true; b = read())
            {
                if (b < '0' || '9' < b)
                    return ng ? -ret : ret;
                else ret = ret * 10 + b - '0';
            }
        }
        public int Integer() { return (int)Long(); }
        public double Double() { return double.Parse(Scan(), CultureInfo.InvariantCulture); }
    }
    public class UnionFind
    {
        public int[] data;

        public UnionFind(int size)
        {
            data = new int[size];
            for (int i = 0; i < size; i++) data[i] = -1;
        }

        public bool Unite(int x, int y)
        {
            x = Root(x);
            y = Root(y);

            if (x != y)
            {
                if (data[y] < data[x])
                {
                    var tmp = y;
                    y = x;
                    x = tmp;
                }
                data[x] += data[y];
                data[y] = x;
            }
            return x != y;
        }

        public bool IsSameGroup(int x, int y)
        {
            return Root(x) == Root(y);
        }

        public int Root(int x)
        {
            return data[x] < 0 ? x : data[x] = Root(data[x]);
        }
    }
}


Measured memory_bytes: 88800