Buying Books 2

Time limit1sMemory limit256 MB

Summary

Find the maximum number of book copies N buyers can purchase from M stores under per-pair purchase limits.

Level: Medium4 of 10
Topics: Graph
Solved: No attempts yet

Problem

N people want to buy the same book. The people are numbered 1 to N, and person j wants $A_j$ copies. M online stores sell the book. The stores are numbered 1 to M, and store i holds $B_i$ copies.

These N people are the only buyers, and the total number of copies the stores hold equals the total number of copies the people want.

How many copies one person buys from one store is limited. Person j can buy at most $C_{ij}$ copies from store i. Given every purchase limit between a store and a person, write a program that finds the largest number of copies that can be bought.

Input

The first line contains the number of people N and the number of online stores M. ( $1 \le N, M \le 100$ )

The second line contains $A_1, A_2, \dots, A_N$ , the number of copies each person wants. ( $1 \le A_j \le 100$ )

The third line contains $B_1, B_2, \dots, B_M$ , the number of copies each store holds. ( $1 \le B_i \le 100$ )

Each of the next M lines contains N numbers and gives the purchase limits. The j-th number on the i-th line is $C_{ij}$ , the largest number of copies person j can buy from store i. ( $0 \le C_{ij} \le 100$ )

$A_1 + \dots + A_N = B_1 + \dots + B_M$ holds.

Output

Print the largest number of copies that can be bought.

Examples7

Example 1

Input

Expected output

Example 2
Input
```
1 1
1
1
1
```
Expected output
```
1
```
Example 3
Input
```
1 1
5
5
0
```
Expected output
```
0
```
Example 4
Input
```
3 2
2 3 4
5 4
9 9 9
9 9 9
```
Expected output
```
9
```
Example 5
Input
```
3 3
4 4 4
4 4 4
5 5 0
5 5 0
5 5 0
```
Expected output
```
8
```
Example 6
Input
```
2 2
3 3
4 2
3 0
3 0
```
Expected output
```
3
```

Example 7

Input

Expected output