测试数据来自 system/2145

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【题目描述】

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

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

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

【输入格式】

　　第一行三个数整数：分别表示队员总重量上限 \(W\)、多多班上学生总人数 \(N\)、女同学人数 \(M\)；
　　第二行一个整数，表示参赛队中女队员人数不少于 \(K\) 人；
　　接下来 \(N\) 行每行两个整数，分别表示多多班上每个同学的重量和力量，其中第 3 到 \(M+2\) 行是所有女生的重量和力量，第 \(M+3\) 到 \(N+2\) 行表示所有男同学的重量和力量，每个整数在 60 至 180 之间。

【输出格式】

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

【输入输出样例】

　Input

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

　Output

460

【子任务】

　　共 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\)

【来源】

　　Mr.he