Problem Description

There are $ P $ male chickens and $ Q $ female chickens.
The males are numbered $1, 2, \dots, P$ and the females are numbered $1, 2, \dots, Q$.
Additionally, a matrix $ S $ of size $ P $ rows and $ Q $ columns consisting only of 0 and 1 is given.
If $ S_{i,j} $, which is the element in the $ i $-th row and $ j $-th column of $ S $, is 1, then male $ i $ and female $ j $ get along well; if it is 0, they do not get along.

Consider forming pairs of male and female chickens that get along well (it is acceptable to have zero pairs). However, the same chicken cannot be included in multiple pairs, and pairs of chickens that do not get along cannot be formed.

After forming the pairs, the happiness of each chicken is determined as follows:

• If male $ i $ is included in any pair, his happiness is $ A_i $; otherwise, it is $ B_i $.
• If female $ i $ is included in any pair, her happiness is $ C_i $; otherwise, it is $ D_i $.

Find the maximum possible total happiness of the $ P + Q $ chickens by forming pairs optimally.

Input Format

The input is given from the standard input in the following format:

$ P $ $ Q $ $S_{1,1}S_{1,2}\ \dots\ S_{1,Q}$ $S_{2,1}S_{2,2}\ \dots\ S_{2,Q}$ $\vdots$ $S_{P,1}S_{P,2}\ \dots\ S_{P,Q}$ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $\dots$ $ A_P $ $ B_P $ $ C_1 $ $ D_1 $ $ C_2 $ $ D_2 $ $\dots$ $ C_Q $ $ D_Q $

Output Format

Output the answer as an integer.

Sample Input and Output

Sample Input #1

4 4
0010
1111
0010
0010
7 4
6 1
4 9
5 3
1 1
2 8
9 4
6 5

Sample Output #1

49

Sample Input #2

3 4
0000
0000
0000
1 2
3 4
5 6
7 8
9 10
11 12
13 14

Sample Output #2

56

Sample Input #3

4 3
100
100
100
111
5 4
3 2
9 8
100 1
200 50
10 9
8 6

Sample Output #3

332

Notes/Hints

Constraints

• $ P, Q, A_i, B_i, C_i, D_i $ are all integers.
• $1 \le P, Q \le 100$
• $ S $ is a matrix of size $ P $ rows and $ Q $ columns consisting only of 0 and 1.
• $1 \le A_i, B_i, C_i, D_i \le 10^9$

Sample Explanation 1

For example, when forming pairs of male $ 1 $ with female $ 3 $ and male $ 2 $ with female $ 4 $, the total happiness is $ 7 + 6 + 9 + 3 + 1 + 8 + 9 + 6 = 49 $, which is optimal.

Sample Explanation 2

It is possible that no pairs can be formed, or it might be optimal not to form any pairs.

见题面 Input 部分

见题面 Output 部分