南郵OJ 1654合宿

合宿
時間制限（一般/Java） : 
1000 MS/ 3000 MS          実行メモリ制限：65536 KByte総提出：87           試験合格：26 
試合の説明
南郵ACM夏休み合宿が始まる。休みの後、学校のスーパーが閉店したので、YMさんは今日スーパーに行って商品を買うことにしました。スーパーには全部でN（1<=N<=15）の商品があります。超市長の時間がないので、商品は一つしか残っていません。i番目の商品の価格はmiです。その実用度はpiです。YMは商品の購入を希望します。総費用はMを超えません。また、スーパーは今日ちょうどキャンペーンがあります。商品の購入にかかる総費用はM 1（=M 1<=10^9）を下回らない限り、スーパーはM 2（=m 2（=10^9）を超えない商品をサービスします。YMが購入したい商品の実用度の合計が一番大きいです。
入力
複数グループでデータを入力します。入力データの各グループの最初の行には、2つの整数NとMがあります。次にN行目、i行目は二つの整数miとpiがあり、i番目の商品の価格と実用性を表します。最後の行は2つの整数M 1とM 2があります。
出力
一組のデータを出力して、Mを超えない場合、購入した商品の最大実用度の合計です。
サンプル入力
3 3 1 2 4 3 5 3 2
サンプル出力
9
ヒント
 
タイトルソース
ym

/* AC 15MS Internet
#include 
#include 
#include 
using namespace std;


struct Item {
    int m;
    int p;
};


struct CmpItem {
    bool operator()(Item const &x, Item const &y) const {
        return x.p < y.p;
    }
};


Item g[17];


int N;
bool buy[20];
int restMoney;
int M, M1, M2;
int P;
int best;


int findGift() {
    int i;
    for (i = N - 1; i >= 0; --i) {
        if (!buy[i] && g[i].m <= M2) return g[i].p;
    }
    return 0;
}


void solve(int x) {
    if (x == N) {
        int cost = M - restMoney;
        if (cost >= M1) {
            best = max(best, P + findGift());
        } else {
            best = max(best, P);
        }
        return;
    }
    buy[x] = false;
    solve(x+1);
    if (restMoney < g[x].m) return;
    buy[x]=true;
    restMoney -= g[x].m;
    P += g[x].p;
    solve(x+1);
    restMoney += g[x].m;
    P -= g[x].p;
}


void input() {
    if (scanf("%d %d", &N, &M) != 2) exit(0);
    int i;
    for (i = 0; i < N; ++i) {
        scanf("%d %d", &(g[i].m), &(g[i].p));
    }
    scanf("%d %d", &M1, &M2);
}


void run() {
    sort(g, g + N, CmpItem());
    best = -2000000000;
    restMoney = M;
    P = 0;
    solve(0);
    printf("%d
", best);
}


int main() {
    while(1) {
        input();
        run();
    }
	return 0;
}
*/








//      93MS
#include
#include
using namespace std;


#define MAX_N 15
int m[MAX_N];
int p[MAX_N];


int main(){
	int N,M,M1,M2,i,k,cm,K,cp,mp;
	while(scanf("%d%d",&N,&M)==2){
		for(i=0;i			scanf("%d%d",m+i,p+i);
		}
		scanf("%d%d",&M1,&M2);
		K = 1<		mp = INT_MIN;
		for(k=0;k			cm = 0;
			cp = 0;
			for(i=0;i				if(k & (1<					cm += m[i];
					if(cm > M){
						break;
					}
					cp += p[i];
				}
			}
			if(cm <= M){
				if(cm >= M1){
					int more=0;
					for(i=0;i						if(!(k&(1<							more = p[i];
						}
					}
					cp += more;
				}
			}
			if(cp > mp){
				mp = cp;
			}
		}
		printf("%d
",mp);
	}
}