// 0-1ナップサック問題
// 重さと価値がそれぞれ、wi,viであるようなn個の品物があります。
// これらの品物から、重さの総和がWを超えないように選んだ時の
// 価値の総和の最大値を求めなさい。
 
 
#include <stdio.h>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
// 入力値の上限
const int MAX_N = 100;		// 品物数の上限
const int MAX_W = 10000;	// 重さの上限の上限
 
// 入力値
int N; // 品物の数
int W; // 重さの上限（制約条件）
int Weight[MAX_N];	// 品物nの重さ
int Value[MAX_N];	// 品物nの価値
 
 
//---------- 枝刈り探索 ----------
int MaxValueEdakari;	// 価値の最大
void dfsEdakari(int n, int totalWeight, int totalValue)
{
	// 枝刈り。重さが上限をすでに超えたときは打ち切り
	if(totalWeight>W)
	{
		return;
	}
 
	// 他にも、残り全部の品物をとったとしても、価値の最大を更新できないとき、ここで枝刈りができる。
 
	if(n==N)
	{
		// 全部の品物を見たので、最大価値の更新
		MaxValueEdakari = max(MaxValueEdakari,totalValue);
		return;
	}
 
	dfsEdakari(n+1, totalWeight+Weight[n], totalValue+Value[n]); // 品物nを取る
	dfsEdakari(n+1, totalWeight, totalValue); // 品物nを取らない
}
 
//---------- メモ化再帰 ----------
int dp[MAX_N][MAX_W]; // dp[n][totalWeight=品物n～N-1番目の合計の重さ]=品物n～N-1番目の価値合計の最大値
int dfsMemo(int n, int totalWeight)
{
	if(n==N)
	{
		// 品物を1つも選んでないので、価値は0
		return 0;
	}
 
	int& memo = dp[n][totalWeight]; // 関数の入力値n,totalWeightを、そのまま配列のindexに使うのがポイント
 
	if(memo>=0)
	{
		// すでに関数の出力は一度計算してメモ化されてるので、即return;
		return memo;
	}
 
	// メモ化する
	memo=0;
 
	// 取る
	if(totalWeight+Weight[n]<=W) // 重さ上限チェック
	{
		memo = max(memo,dfsMemo(n+1, totalWeight+Weight[n])+Value[n]);
	}
 
	// 取らない
	memo = max(memo,dfsMemo(n+1, totalWeight));
 
	return memo;
}
 
 
int main()
{
	// 入力
	cin >> N >> W;
	for (int n = 0; n < N; n++)
	{
		cin >> Weight[n] >> Value[n];
	}
 
	//---------- 枝刈り探索 ----------
	MaxValueEdakari = -1;
	dfsEdakari(0,0,0);
 
	//---------- メモ化再帰 ----------
	for (int n = 0; n < MAX_N; n++)
	{
		for (int w = 0; w < MAX_W; w++)
		{
			dp[n][w]=-1;
		}
	}
	const int MaxValueMemo = dfsMemo(0,0);
 
	// 出力
	cout << " MaxValueEdakari=" << MaxValueEdakari << " MaxValueMemo=" << MaxValueMemo << endl;
 
	return 0;
}
 

Ly8gMC0x44OK44OD44OX44K144OD44Kv5ZWP6aGMCi8vIOmHjeOBleOBqOS+oeWApOOBjOOBneOCjOOBnuOCjOOAgXdpLHZp44Gn44GC44KL44KI44GG44GqbuWAi+OBruWTgeeJqeOBjOOBguOCiuOBvuOBmeOAggovLyDjgZPjgozjgonjga7lk4HnianjgYvjgonjgIHph43jgZXjga7nt4/lkozjgYxX44KS6LaF44GI44Gq44GE44KI44GG44Gr6YG444KT44Gg5pmC44GuCi8vIOS+oeWApOOBrue3j+WSjOOBruacgOWkp+WApOOCkuaxguOCgeOBquOBleOBhOOAggogCiAKI2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGFsZ29yaXRobT4KIAp1c2luZyBuYW1lc3BhY2Ugc3RkOwogCi8vIOWFpeWKm+WApOOBruS4iumZkApjb25zdCBpbnQgTUFYX04gPSAxMDA7CQkvLyDlk4HnianmlbDjga7kuIrpmZAKY29uc3QgaW50IE1BWF9XID0gMTAwMDA7CS8vIOmHjeOBleOBruS4iumZkOOBruS4iumZkAogCi8vIOWFpeWKm+WApAppbnQgTjsgLy8g5ZOB54mp44Gu5pWwCmludCBXOyAvLyDph43jgZXjga7kuIrpmZDvvIjliLbntITmnaHku7bvvIkKaW50IFdlaWdodFtNQVhfTl07CS8vIOWTgeeJqW7jga7ph43jgZUKaW50IFZhbHVlW01BWF9OXTsJLy8g5ZOB54mpbuOBruS+oeWApAogCiAKLy8tLS0tLS0tLS0tIOaeneWIiOOCiuaOoue0oiAtLS0tLS0tLS0tCmludCBNYXhWYWx1ZUVkYWthcmk7CS8vIOS+oeWApOOBruacgOWkpwp2b2lkIGRmc0VkYWthcmkoaW50IG4sIGludCB0b3RhbFdlaWdodCwgaW50IHRvdGFsVmFsdWUpCnsKCS8vIOaeneWIiOOCiuOAgumHjeOBleOBjOS4iumZkOOCkuOBmeOBp+OBq+i2heOBiOOBn+OBqOOBjeOBr+aJk+OBoeWIh+OCigoJaWYodG90YWxXZWlnaHQ+VykKCXsKCQlyZXR1cm47Cgl9CiAKCS8vIOS7luOBq+OCguOAgeaui+OCiuWFqOmDqOOBruWTgeeJqeOCkuOBqOOBo+OBn+OBqOOBl+OBpuOCguOAgeS+oeWApOOBruacgOWkp+OCkuabtOaWsOOBp+OBjeOBquOBhOOBqOOBjeOAgeOBk+OBk+OBp+aeneWIiOOCiuOBjOOBp+OBjeOCi+OAggogCglpZihuPT1OKQoJewoJCS8vIOWFqOmDqOOBruWTgeeJqeOCkuimi+OBn+OBruOBp+OAgeacgOWkp+S+oeWApOOBruabtOaWsAoJCU1heFZhbHVlRWRha2FyaSA9IG1heChNYXhWYWx1ZUVkYWthcmksdG90YWxWYWx1ZSk7CgkJcmV0dXJuOwoJfQogCglkZnNFZGFrYXJpKG4rMSwgdG90YWxXZWlnaHQrV2VpZ2h0W25dLCB0b3RhbFZhbHVlK1ZhbHVlW25dKTsgLy8g5ZOB54mpbuOCkuWPluOCiwoJZGZzRWRha2FyaShuKzEsIHRvdGFsV2VpZ2h0LCB0b3RhbFZhbHVlKTsgLy8g5ZOB54mpbuOCkuWPluOCieOBquOBhAp9CiAKLy8tLS0tLS0tLS0tIOODoeODouWMluWGjeW4sCAtLS0tLS0tLS0tCmludCBkcFtNQVhfTl1bTUFYX1ddOyAvLyBkcFtuXVt0b3RhbFdlaWdodD3lk4Hnialu772eTi0x55Wq55uu44Gu5ZCI6KiI44Gu6YeN44GVXT3lk4Hnialu772eTi0x55Wq55uu44Gu5L6h5YCk5ZCI6KiI44Gu5pyA5aSn5YCkCmludCBkZnNNZW1vKGludCBuLCBpbnQgdG90YWxXZWlnaHQpCnsKCWlmKG49PU4pCgl7CgkJLy8g5ZOB54mp44KSMeOBpOOCgumBuOOCk+OBp+OBquOBhOOBruOBp+OAgeS+oeWApOOBrzAKCQlyZXR1cm4gMDsKCX0KIAoJaW50JiBtZW1vID0gZHBbbl1bdG90YWxXZWlnaHRdOyAvLyDplqLmlbDjga7lhaXlipvlgKRuLHRvdGFsV2VpZ2h044KS44CB44Gd44Gu44G+44G+6YWN5YiX44GuaW5kZXjjgavkvb/jgYbjga7jgYzjg53jgqTjg7Pjg4gKIAoJaWYobWVtbz49MCkKCXsKCQkvLyDjgZnjgafjgavplqLmlbDjga7lh7rlipvjga/kuIDluqboqIjnrpfjgZfjgabjg6Hjg6LljJbjgZXjgozjgabjgovjga7jgafjgIHljbNyZXR1cm47CgkJcmV0dXJuIG1lbW87Cgl9CiAKCS8vIOODoeODouWMluOBmeOCiwoJbWVtbz0wOwogCgkvLyDlj5bjgosKCWlmKHRvdGFsV2VpZ2h0K1dlaWdodFtuXTw9VykgLy8g6YeN44GV5LiK6ZmQ44OB44Kn44OD44KvCgl7CgkJbWVtbyA9IG1heChtZW1vLGRmc01lbW8obisxLCB0b3RhbFdlaWdodCtXZWlnaHRbbl0pK1ZhbHVlW25dKTsKCX0KIAoJLy8g5Y+W44KJ44Gq44GECgltZW1vID0gbWF4KG1lbW8sZGZzTWVtbyhuKzEsIHRvdGFsV2VpZ2h0KSk7CiAKCXJldHVybiBtZW1vOwp9CiAKIAppbnQgbWFpbigpCnsKCS8vIOWFpeWKmwoJY2luID4+IE4gPj4gVzsKCWZvciAoaW50IG4gPSAwOyBuIDwgTjsgbisrKQoJewoJCWNpbiA+PiBXZWlnaHRbbl0gPj4gVmFsdWVbbl07Cgl9CiAKCS8vLS0tLS0tLS0tLSDmnp3liIjjgormjqLntKIgLS0tLS0tLS0tLQoJTWF4VmFsdWVFZGFrYXJpID0gLTE7CglkZnNFZGFrYXJpKDAsMCwwKTsKIAoJLy8tLS0tLS0tLS0tIOODoeODouWMluWGjeW4sCAtLS0tLS0tLS0tCglmb3IgKGludCBuID0gMDsgbiA8IE1BWF9OOyBuKyspCgl7CgkJZm9yIChpbnQgdyA9IDA7IHcgPCBNQVhfVzsgdysrKQoJCXsKCQkJZHBbbl1bd109LTE7CgkJfQoJfQoJY29uc3QgaW50IE1heFZhbHVlTWVtbyA9IGRmc01lbW8oMCwwKTsKIAoJLy8g5Ye65YqbCgljb3V0IDw8ICIgTWF4VmFsdWVFZGFrYXJpPSIgPDwgTWF4VmFsdWVFZGFrYXJpIDw8ICIgTWF4VmFsdWVNZW1vPSIgPDwgTWF4VmFsdWVNZW1vIDw8IGVuZGw7CiAKCXJldHVybiAwOwp9Cg==

NQoxMDAKNzggMjUKMTYgOTAKMzAgMjkKNDAgODAKNSAxOCA=

5
100
78 25
16 90
30 29
40 80
5 18