Maximizing Distinct Total Cube Counts

You are given a set of unit cube blocks and two views of a 3D structure: a front view (also called the main view) and a left view. However, some columns in the front view are hidden so that you cannot observe their heights. For each hidden column, you can choose its height arbitrarily (as any positive integer) before constructing the structure.

Once the heights of all columns (both observed and chosen for the hidden ones) are determined, the structure is built using the minimal number of cubes such that its front and left views exactly match the given numbers. More precisely, assume the structure is arranged in an n × m grid. The front view is an array F of length n and the left view is an array L of length m. For every column i with a fixed value (i.e. not hidden), the height is given by F[i]. For hidden columns, represented by -1 in the input, you may assign any positive integer. The structure is then constructed in such a way that in the cell at row j and column i you place min( h[i], L[j] ) cubes, where h[i] is the final (fixed or chosen) height of column i. In other words, the total number of cubes used is

[ k = \sum_{i=1}^{n} \sum_{j=1}^{m} \min( h[i], L[j] ) ]

Note that for columns with a hidden value you decide on h[i] (which can be any positive integer) and consequently you determine their contribution to k. Let the number of hidden columns be r. For any hidden column, if you choose a value x, its contribution is exactly

[ f(x)=\sum_{j=1}^{m} \min(x, L_j).]

Since the left view L is fully known, define (M = \max{L_1, L_2, \dots, L_m}). Observe that for any choice, when (x \ge M), (f(x)) becomes constant (\sum_{j=1}^{m}L_j). Thus, for each hidden column, there are exactly M distinct possible contributions corresponding to choices (x=1,2,\dots,M) (note that (f(x)) is strictly increasing for (x) from 1 to (M)).

Your task is to choose values for the hidden columns (each independently chosen from \(\{1,2,\dots,M\}\)) so that overall the total number of cubes used in the structure, k, may take as many distinct integer values as possible. In other words, let the fixed columns (with observed heights) contribute a constant C (computed as \(\sum_{\text{fixed } i} f(F[i])\)) and let the r hidden columns contribute values independently chosen from the set

[ A = {f(1), f(2), \dots, f(M)}. ]

Then the distinct totals reachable are

[ C + S, \quad\text{where } S \text{ is any sum of } r \text{ numbers from } A.]

Determine the maximum number of distinct integer values that k can take.

Input/Output Note. The constant C does not affect the number of distinct possibilities since it is added to every sum. Hence, your task reduces to computing the number of distinct sums that can be formed by selecting r elements (with repetition allowed) from the set A.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 50), representing the number of columns in the front view and the number of rows in the left view respectively.

The second line contains n integers, each either a positive integer (at most 50) or -1. A positive integer indicates a fixed height of the corresponding column in the front view, while -1 indicates that the height is hidden and you may assign any positive integer.

The third line contains m positive integers (each at most 50), representing the left view.

outputFormat

Output a single integer — the maximum possible number of distinct values of k (the total number of cubes) that can be obtained by an appropriate selection of heights for the hidden columns.

sample

3 2
-1 2 -1
3 4

9