Preparing NOJ

集训

1000ms 65536K

Description:

南邮ACM暑期集训即将开始。由于放假后,学校的超市关闭营业,YM同学决定今天去超市购买一些商品。超市中一共有N1<=N<=15)种商品,因为超市长时间没有进货,导致每种商品都仅剩下一件。第i种商品的价格为mi(1<=mi<=10^9),它的实用度为pi0<=pi<=10000)。YM希望购买商品的总花费不超过M0<=M<=10^9)。同时,超市今天正好有促销活动,只要购买商品的总花费不低于M10<=M1<=10^9),超市将赠送一件价格不超过M20<=m2<=10^9)的商品。YM希望购买的商品实用度的总和最大。

Input:

多组输入数据。每组输入数据第一行有两个整数NM。接下来N行,第i行有两个整数mipi,表示第i件商品的价格和实用度。最后一行有两个整数M1M2

Output:

每组数据输出一行,在花费不超过M的情况下,购买的商品最大的实用度总和。

Sample Input:

3 3
1 2
2 4
3 5
3 2

Sample Output:

9

Note:

 

本题由旧版NOJ导入,来源:ym

Info

NOJ

Provider NOJ

Code NOJ1654

Tags

Submitted 3

Passed 1

AC Rate 33.33%

Date 04/20/2019 10:03:10

Related

Nothing Yet