在我们下饭店的时候蛤玮经常负责点菜,今天饭店搞活动,当总价格大于等于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".