问题陈述
给你一个整数集 S=\{S_1,S_2,\ldots,S_N\} 尺寸 N 和一个序列 D=(D_1,D_2,\ldots,D_{M-1}) 长度 (M-1).
其中长度-M 序列 A 由以下元素组成 S,找到最大整数个数 i 之间 1 和 (M-1),包含在内,这样 |A_i-A_{i+1}| = D_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),有四个整数 i 与 |A_i-A_{i+1}|=D_i。这个计数永远不可能 5 或更大,所以答案是 4.
示例输入 2
10 7 22 75 26 45 72 81 47 29 97 2 0 30 34 0 18 50
示例输出 2
5