Description

学校决定举行一次全校性的拔河比赛，以班为单位组队。我们知道影响拔河比赛胜负的因素有：参赛队的合力量，总重量和技巧。如果每只队伍人数都一样的话，那么低年级的班级会没有获胜的希望。因此学校考虑到比赛公平性和参与的广泛性，做出如下规定：

1.每只队伍的人数不一定相同，但队员的总重量不能超过某个规定的值。

2.每只队伍的女队员不少于一定的人数。

多多是高二.1班的体育委员，班主任将本班组队的任务交给了他。多多深知影响比赛胜败的三个关键因素中力量和重量是前提，技巧靠后期训练。因此他必须先考虑在学校规定的前提下，选那些同学才能获得最大的合力量。

$5_2$

$5^2$

${1}^{1}$

$\sqrt[5]{2}$

Input Format

第一行三个整数：分别表示队员重量上限W，多多班上学生总人数N，女同学人数M；

第二行一个整数，表示参赛队中女队员人数不少于K人；

接下来N行每行两个整数，分别表示多多班上每个同学的重量和力量，其中第3到M+2行是所有女生的重量和力量，第M+3到N+2行表示所有男同学的重量和力量，每个整数在60至180之间

Output Format

一行一个整数，合力量的最大值

400 10 3
2
90 120
80 90
100 150
110 80
150 100
120 80
90 80
80 70
120 100
110 90

460

Hint

共10组测试数据：

对于前3组测试数据有N≤20、K≤M≤10、W≤1000

对于前5组测试数据有N≤30、K≤M≤15、W≤2000

对于前10组测试数据有N≤100、K≤M≤50、W≤10000

Source

信奥星OJ http://127.0.0.1