#30 「 魔法棋盘 」

统计

R君得到了一个魔法棋盘,它由n行m列组成。

在这个魔法棋盘上一共有k个魔法球,每个魔法球都在棋盘不同的格子里。

R君想要启动这个魔法棋盘,他可以激活这个棋盘的一些行和一些列。

每行和每列都可以选择激活或者是不激活,如果激活的话需要消耗一定的魔法值,激活第i行需要消耗$wr_i$的魔法值,激活第i列需要消耗$wc_i$的魔法值。

对于行和列激活的状态不同,会导致魔法球的效果不同。

具体来说:

如果一个魔法球所在的行和列都没有被激活,那么这个魔法球会产出$w_N$的魔法值。

如果一个魔法球所在的行被激活,所在的列没有被激活,那么这个魔法球会产出$w_R$的魔法值。

如果一个魔法球所在的列被激活,所在的行没有被激活,那么这个魔法球会产出$w_C$的魔法值。

如果一个魔法球所在的行被激活,所在的列也被激活,那么这个魔法球会产出$w_A$的魔法值。

($wr_i, wc_i ,w_N, w_R , w_C, w_A$均为整数,可正可负)

启动这个棋盘产出的魔法值是所有魔法球产出的魔法值的和减去激活行和列所消耗的魔法值。

现在R君想知道启动这个魔法棋盘最多可以产出多少魔法值。

输入格式

第一行三个整数n,m,k。

接下来一行n个整数,表示$wr_i$。

接下来一行m个整数,表示$wc_i$。

接下来一行四个整数$w_N, w_R , w_C, w_A$。

接下来k行,每行两个数字x, y,表示有一个魔法球在x行y列。

输出格式

输出包含一个整数,表示答案。

样例数据

input

2 2 3
5 100
5 100
-10 20 20 -10
1 1
1 2
2 1

output

25

数据规模与约定

$1 \le n,m \le 1000, 0 \le k \le 2000 $, $-100 \le wr_i, wc_i ,w_N, w_R , w_C, w_A \le 100$。

时间限制:1s

空间限制:512MB

Author: zrt