Counting Cows with Wind-Carried Mooing

Farmer John has forgotten the exact number of cows he owns. Too embarrassed to count them directly in the fields, he secretly records the total mooing volume in each of his N fields which are arranged in a line along a straight road.

Each field may contain cows from B different breeds. A cow of breed i moos at a volume of \(V_i\) (\(1 \le V_i \le 100\)). Due to a strong wind blowing from left to right, mooing from one field carries over to the next field. Specifically, if a field records a total mooing volume of \(X\), then the wind carries a volume of \(\max(X-1,0)\) into the next field. Thus, if the direct contribution of cows in field 1 is \(A_1\) (so that the total volume in field 1 is \(A_1\)), then for each field \(i\) (\(2 \le i \le N\)) the total recorded volume is:

\[ \text{reading}_i = A_i + \begin{cases}0, & i=1\\ \max(\text{reading}_{i-1}-1,0), & i>1\end{cases} \]

You are given the total recorded mooing volume in each of the N fields and the mooing volume of each breed. In every field the cows that are present produce a volume that can be expressed as a nonnegative integer linear combination of the breed volumes. Your task is to determine the minimum total number of cows that Farmer John might own. If it is impossible to achieve the recorded configuration, output -1.

Note: For field 1, \(A_1 = \text{reading}_1\). For \(i \ge 2\), the direct cows' contribution in field \(i\) is:

\[ A_i = \text{reading}_i - \max(\text{reading}_{i-1}-1,0). \]

For each field, you must represent \(A_i\) as a sum \(\sum_{j=1}^{B} x_j \cdot V_j\) with nonnegative integers \(x_j\), and you want to minimize \(\sum_{i=1}^{N} \sum_{j=1}^{B} x_j\).

inputFormat

The input consists of multiple lines. The first line contains two space‑separated integers \(N\) and \(B\) where \(1 \le N \le 100\) and \(1 \le B \le 20\). The next \(B\) lines each contain an integer \(V_i\) (the mooing volume of breed \(i\), \(1 \le V_i \le 100\)). The following \(N\) lines each contain an integer representing the total recorded mooing volume in each field. It is guaranteed that the direct mooing volume produced by cows in any field does not exceed \(10^5\).

outputFormat

Output a single line containing the minimum total number of cows. If it is impossible to obtain the recorded configuration, output -1.

sample

3 2
3
4
3
5
8

3