7992: ABC255 —— E - Lucky Numbers
[Creator : ]
Description
You are given a sequence of N−1 integers $S=(S_1,S_2,…,S_{N−1})$, and M distinct integers $X_1,X_2,…,X_M$, which are called lucky numbers.
A sequence of N integers $A=(A_1,A_2,…,A_N)$ satisfying the following condition is called a good sequence.
A sequence of N integers $A=(A_1,A_2,…,A_N)$ satisfying the following condition is called a good sequence.
$A_i+_{Ai+1}=S_i$ holds for every i=1,2,…,N−1.Find the maximum possible number of terms that are lucky numbers in a good sequence A, that is, the maximum possible number of integers i between 1 and N such that $A_i\in {X_1,X_2,…,X_M}$.
Input
Input is given from Standard Input in the following format:
$N\ M$
$S_1\ S_2\ …\ S_{N−1}$
$X_1\ X_2\ …\ X_M$
$N\ M$
$S_1\ S_2\ …\ S_{N−1}$
$X_1\ X_2\ …\ X_M$
Output
Print the maximum possible number of terms that are lucky numbers in a good sequence A.
Constraints
$2≤N≤10^5$
$1≤M≤10$
$−10^9≤S_i≤10^9$
$−10^9≤X_i≤10^9$
$X_1<X_2<⋯<X_M$
All values in input are integers.
$1≤M≤10$
$−10^9≤S_i≤10^9$
$−10^9≤X_i≤10^9$
$X_1<X_2<⋯<X_M$
All values in input are integers.
Sample 1 Input
9 2
2 3 3 4 -4 -7 -4 -1
-1 5
Sample 1 Output
4
A good sequence A=(3,−1,4,−1,5,−9,2,−6,5) contains four terms that are lucky numbers: $A_2,A_4,A_5,A_9$, which is the maximum possible count.
Sample 2 Input
20 10
-183260318 206417795 409343217 238245886 138964265 -415224774 -499400499 -313180261 283784093 498751662 668946791 965735441 382033304 177367159 31017484 27914238 757966050 878978971 73210901
-470019195 -379631053 -287722161 -231146414 -84796739 328710269 355719851 416979387 431167199 498905398
Sample 2 Output
8