← 返回题目列表

AtCoder · past21_m

M. 差异限制序列

中文机器翻译题面 查看原题

问题陈述

给你一个整数集 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