题目描述
又到了十月一号了，今年十一居然是8天连休，wd早早的回到了家里，盘算着十月一号怎么过。作为一名dota狂热爱好者，打dota必然是他的首选任务。不过wd毕竟是学霸，作业还是要做的，书还是要看的。那么问题就来了，如何学习dota两不误。就个人管理而言，wd向来是饱受诟病的，于是他又想到了kk。wd告诉kk他在假期里想完成的n个学习任务，在这些任务中，他在这个假期至少要做m件，每件任务都有一个耗时，并且对于每个任务，wd都给出了一个好感度（顺便说一句，wd与zy是同一个中学的）。同时，这个假期的总时间是有限的，为T，他最少需要用来打dota的时间是t，而且，打dota的每个单位时间都有好感度g。现在，你要告诉wd，在至少打t时间dota，并完成至少m个任务的前提下，他所能获得的最大好感度。
输入
第一行两个整数n,m。
接下来n行每行两个整数ti,gi，表示每个任务的时间和好感度。
最后一行三个整数T,t,g。
输出
一行一个整数，表示最大好感度。如果没有符合的方案，则输出0。
样例输入
2 1
2 4
3 6
10 5 1
样例输出
15
数据范围限制
0<=m<=n<=20。
0<=t<=T
vara:array[0..100,1..2]of longint;i,t,n,m,d,g,ans:longint;
procedure dfs(x,y,z,p:longint);
beginif n-p+1<x then exit;if x=0 thenif z+y*g>ans then ans:=z+y*g;if x=0 then exit;if a[p,1]<=y thendfs(x-1,y-a[p,1],z+a[p,2],p+1);dfs(x,y,z,p+1);
end;
beginassign(input,'holiday.in');reset(input);assign(output,'holiday.out');rewrite(output);readln(n,m);for i:=1 to n doreadln(a[i,1],a[i,2]);readln(t,d,g);for i:=m to n dodfs(i,t-d,d*g,1);writeln(ans);close(input);close(output);
end.