import std.stdio;
import std.conv;
import std.array;
import std.algorithm;

struct Item {
    int w;
    int v;
}

void main()
{
    auto buf = readln.split;
    int N = buf[0].to!int;
    int W = buf[1].to!int;
    Item[] items = new Item[N];
    foreach (i; 0..N){
        buf = readln.split;
        items[i].w = buf[0].to!int;
        items[i].v = buf[1].to!int;
    }

    long[] sum_v = new long[W + 1];
    foreach (i; 0..N){
        int v = items[i].v;
        int w = items[i].w;
        for (uint j = W; j > 0; j--){
            if (j < items[i].w) break;
            
            long sum_i = sum_v[j - w] + v;
            if (sum_i > sum_v[j]) sum_v[j] = sum_i;
        }
    }

    writeln(sum_v[W]);
}

