Migrated from Lutece 159 解救小P

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

比赛暂告一段落，YDX总算有时间可以玩一下小P了。这段时间出了很多新游戏，可是YDX一看记忆棒已经被塞满了，只好忍痛割爱删掉一些游戏了。正在慢慢挑选游戏的YDX突然接到一电话，有急事要出门去了。现在YDX只有时间进行最多L次操作了（删除或者添加一个游戏都算作一次操作），你能帮助YDX选选游戏吗？

Input

第一行包括一个整数$T$（$T\leq 10$），表示测试数据的组数。

每组数据第一行包括四个整数$M$，$L$，$n_1$，$n_2$（$1\leq n_1, n_2\leq 30$，$0\leq L\leq n_1+n_2$，$1\leq M\leq 1,000$），分别表示记忆棒的容量，可以进行的操作次数，记忆棒上原有的游戏个数，待添加的游戏个数。

接下来$n_1$行每行描述一个记忆棒上原有的游戏，包括两个整数$m$,$f$（$1\leq m,f\leq 1,000$），分别表示游戏的容量大小和YDX对它的喜爱程度。

接下来$n_2$行每行描述一个待选的游戏，格式同上。

数据保证记忆棒上原有游戏的容量总和小于等于$M$。

Output

请在满足题目要求的情况下使得最终记忆棒上的游戏f值之和最大。每组数据输出一行，包括这个最大值。

Samples

3
10 2 1 1
9 5
10 6
9 2 1 1
9 5
10 6
10 1 1 1
9 5
10 6

6
5
5

Note

第一组数据：将游戏$(9,5)$删除，添加游戏$(10,6)$即可，使用了两次操作

第二组数据：因为记忆棒容量只有$9$，所以无法添加游戏$(10,6)$。最好情况就是什么都不做

第三组数据：因为只有一次操作，所以无法添加游戏$(10,6)$。最好情况就是什么都不做

Resources

stephydx