Sugarcane Trimming

Xiaolan has planted a row of sugarcanes. There are n sugarcanes, and the height of the i-th sugarcane is \(a_i\). He wants to cut some of the sugarcanes to taste them, but because of his compulsive disorder, he doesn’t want the heights of the sugarcanes to look messy. Specifically, he is given a set of m integers \(B = \{b_1, b_2, \dots, b_m\}\). After he cuts the sugarcanes, for every pair of adjacent sugarcanes the absolute height difference, \(|a_i - a_{i+1}|\), must be an element of \(B\).

For each sugarcane of height \(h\), Xiaolan can cut it down to any height \(x\) such that \(x \in \{0, 1, 2, \dots, h-1\}\) (if he does not cut it, its height remains \(h\), and no cost is incurred). He wants to know the minimum number of sugarcanes that need to be cut so that the condition on adjacent differences is met. If it is impossible to achieve, output -1.

Note: There is no constraint between the first sugarcane and any previous one.

inputFormat

The first line contains two integers \(n\) and \(m\) (1 \leq n \leq 1000, small heights assumed) — the number of sugarcanes and the size of the set \(B\), respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the heights of the sugarcanes.

The third line contains \(m\) integers \(b_1, b_2, \dots, b_m\) representing the allowed absolute differences.

outputFormat

Output a single integer — the minimum number of sugarcanes that must be cut so that for every two adjacent sugarcanes, the absolute height difference belongs to \(B\). If it is impossible to achieve, output -1.

sample

3 2
5 3 6
2 3

0