问题 G: 蛤玮点菜

问题 G: 蛤玮点菜

时间限制: 2 Sec  内存限制: 128 MB
提交: 347  解决: 40
[状态] [讨论版] [提交] [命题人:]
题目描述
在我们下饭店的时候蛤玮经常负责点菜,今天饭店搞活动,当总价格大于等于X时可以减去Y的优惠,注意如果总价是2X也仅减去一倍Y.蛤玮非常了解菜品也了解大家,他知道每个菜品有一个饱食度,只有菜品饱食度的和不小于K时大家才会吃的开心.请问蛤玮如何点菜才能在让大家吃的开心的前提下花尽量少的钱,输出最后需要付的钱.注意蛤玮是个有追求的人,所以他不会点重复的菜.
输入
T(1<=T<=40),表示数据组数.
每组数据第一行n(1<=n<=30),K,X,Y(1<=K,X,Y<=1e9, X>=Y),表示一共有n种菜,X,Y,K如题目中描述.
接下来n行每行两个数ai,bi(1<=ai,bi<=1e8),分别表示第i个菜的价格和饱食度.
输出
每组数据输出一个数,表示总价.如果无解则输出"go die".
样例输入 Copy
1
2 2 20 12
10 2
10 2
样例输出 Copy
8
提示

不可以通过白给店家钱而不买任何东西来得到减价优惠.