Maximum Divine Power with Large Scallions and Drawers

Given \(N\) large scallions and \(M\) drawers, each scallion has a volume \(a_i\) and each drawer has a capacity \(b_j\). Placing the \(i\)-th scallion into the \(j\)-th drawer generates a divine power of \(w_{i,j}\). A drawer can accommodate a set of scallions if the sum of their volumes does not exceed its capacity, and a scallion cannot be split between drawers. Find the maximum divine power that can be achieved by optimally placing the scallions into the drawers.

Note: For the purpose of this problem, it is assumed that \(N\) and \(M\) are small (for example, \(1 \le N, M \le 10\)) so that a solution using bitmask dynamic programming is feasible.

inputFormat

The first line contains two integers \(N\) and \(M\).

The second line contains \(N\) integers: \(a_1, a_2, \dots, a_N\) denoting the volume of each scallion.

The third line contains \(M\) integers: \(b_1, b_2, \dots, b_M\) denoting the capacity of each drawer.

The next \(N\) lines each contain \(M\) integers. The \(j\)-th integer in the \(i\)-th line is \(w_{i,j}\), which denotes the divine power gained by placing the \(i\)-th scallion into the \(j\)-th drawer.

outputFormat

Output a single integer: the maximum divine power that can be obtained.

sample

3 2
1 2 3
3 3
1 2
2 1
3 4

7