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

---

【题目描述】

　　FJ在解决著名的背包问题后兴奋不已，打算向自己的奶牛们炫耀自己的丰功伟绩。可是，一头不服气的奶牛突然跳了出来，给FJ出了一道“新背包问题”：

　　设FJ拥有一个体积为 \(V\) 的背包和 \(N\) 个物品，第 \(i\) 个物品的体积是 \(V_i\) ，价值是 \(P_i\) ，现在要在这 \(N\) 个物品中选出一些体积和不超过 \(V\) 的物品放入这个背包中，使得这些物品的价值和最大。值得注意的是，在这 \(N\) 个物品里有 \(M\) 对完全不同的物品，如果将第 \(i\) 对物品放入背包中，那么这对物品的价值和会增加 \(C_i\)。

【输入格式】

　　第一行两个整数 \(N,M\) 和 \(V\)，分别表示物品的数量，物品对的数量，背包的容积
　　第二行有 \(N\) 个数，第 \(i\) 个数表示第 \(i\) 个物品体积
　　第三行有 \(N\) 个数，第 \(i\) 个数表示第 \(i\)个物品价值
　　第四至第 \(M+4\) 行为两个数 \(x\) 和 \(y\)，第 \(i\) 行表示 \(x\) 和 \(y\) 是第 \(i-3\)对
　　第 \(M+5\) 行有 \(M\) 个数，第 \(i\) 个数表示将第 \(i\) 对物品放入背包后增加的价值

【输出格式】

　　仅包括一行，为背包中物品的最大价值和。

【输入输出样例】

　Input

5 2 20
5 3 5 2 4
4 6 4 2 6
1 2
3 4
4 2

　Output

28

【数据限制】

　　对于 \(50\%\) 的数据，\(1≤N≤20\)，\(V≤1000\)
　　对于 \(100\%\) 的数据，\(1≤N≤1000\)，\(V≤50000\)，\(M≤N/2\) 所有变量均在 int 范围内

【来源】

　　Mr.he