/ 
実行時間制限: 3 sec / メモリ制限: 1024 MiB
問題文
大きさ N の整数の集合 S=\{S_1,S_2,\ldots,S_N\} と長さ M-1 の数列 D=(D_1,D_2,\ldots,D_{M-1}) が与えられます。
S の要素からなる長さ M の数列 A のうち、|A_i-A_{i+1}| = D_i を満たす 1 以上 M-1 以下の整数 i の個数として考えられる最大値を求めてください。
制約
- 1 \leq N \leq 2000
- 2 \leq M \leq 2000
- 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
- 0 \leq D_i \leq 10^9 (1 \leq i \leq M-1)
- S_i \neq S_j (1 \leq i < j \leq N)
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N M
S_1 S_2 ... S_N
D_1 D_2 ... D_{M-1}
出力
答えを出力せよ。
入力例 1
5 5 1 2 3 4 5 3 1 4 1
出力例 1
4
A=(5,2,1,5,4) のとき、|A_i-A_{i+1}|=D_i を満たす i は 4 個あります。この値が 5 以上になることはないため、答えは 4 です。
入力例 2
10 7 22 75 26 45 72 81 47 29 97 2 0 30 34 0 18 50
出力例 2
5
Problem Statement
You are given an integer set S=\{S_1,S_2,\ldots,S_N\} of size N and a sequence D=(D_1,D_2,\ldots,D_{M-1}) of length (M-1).
Among the length-M sequences A consisting of the elements in S, find the maximum number of integers i between 1 and (M-1), inclusive, such that |A_i-A_{i+1}| = D_i.
Constraints
- 1 \leq N \leq 2000
- 2 \leq M \leq 2000
- 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
- 0 \leq D_i \leq 10^9 (1 \leq i \leq M-1)
- S_i \neq S_j (1 \leq i < j \leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
S_1 S_2 ... S_N
D_1 D_2 ... D_{M-1}
Output
Print the answer.
Sample Input 1
5 5 1 2 3 4 5 3 1 4 1
Sample Output 1
4
When A=(5,2,1,5,4), there are four integers i with |A_i-A_{i+1}|=D_i. This count can never be 5 or larger, so the answer is 4.
Sample Input 2
10 7 22 75 26 45 72 81 47 29 97 2 0 30 34 0 18 50
Sample Output 2
5