有 个工作， 种机器，每种机器你可以租或者买过来。
每个工作包括若干道工序，每道工序需要某种机器来完成。
现在给出这些参数，求最大利润。
第一行两个整数 。
下面将有 块数据，对于第 块数据：
第一行给出 表示完成这个任务能赚到的钱及有多少道工序。
接下来 行每行两个数，分别描述完成工序所需要的机器编号 及租用它的费用 。
最后 行，第 行给出购买机器 的费用 。
一行一个整数表示最大能获得的利润。
2 3 100 2 1 30 2 20 100 2 1 40 3 80 50 80 110
50
对于 的数据，，，。
