Polycarp watched TV-show where k jury members one by one rated a participant by adding him a certain number of points (may be negative, i. e. points were subtracted). Initially the participant had some score, and each the marks were one by one added to his score. It is known that the i-th jury member gave a_{i} points.

Polycarp does not remember how many points the participant had before this k marks were given, but he remembers that among the scores announced after each of the k judges rated the participant there were n (n ≤ k) values b_1, b_2, ..., b_{n} (it is guaranteed that all values b_{j} are distinct). It is possible that Polycarp remembers not all of the scores announced, i. e. n < k. Note that the initial score wasn't announced.

Your task is to determine the number of options for the score the participant could have before the judges rated the participant.


-----Input-----

The first line contains two integers k and n (1 ≤ n ≤ k ≤ 2 000) — the number of jury members and the number of scores Polycarp remembers.

The second line contains k integers a_1, a_2, ..., a_{k} ( - 2 000 ≤ a_{i} ≤ 2 000) — jury's marks in chronological order.

The third line contains n distinct integers b_1, b_2, ..., b_{n} ( - 4 000 000 ≤ b_{j} ≤ 4 000 000) — the values of points Polycarp remembers. Note that these values are not necessarily given in chronological order.


-----Output-----

Print the number of options for the score the participant could have before the judges rated the participant. If Polycarp messes something up and there is no options, print "0" (without quotes).


-----Examples-----
Input
4 1
-5 5 0 20
10

Output
3

Input
2 2
-2000 -2000
3998000 4000000

Output
1



-----Note-----

The answer for the first example is 3 because initially the participant could have  - 10, 10 or 15 points.

In the second example there is only one correct initial score equaling to 4 002 000.

Difficulty: interview

Starter code:

Solutions:
def main():
    from sys import stdin
    k, n = map(int, stdin.readline().split())
    a = list(map(int, stdin.readline().split()))
    b = list(map(int, stdin.readline().split()))
    res = set()
    for i in range(k):
        # putting b[0] on place i
        our = set()
        curr = b[0]
        for j in range(i, -1, -1):
            our.add(curr)
            curr -= a[j]
        first = curr
        good = True
        curr = b[0]
        for j in range(i + 1, k):
            curr += a[j]
            our.add(curr)
        for elem in b:
            if elem not in our:
                good = False
                break
        if good:
            res.add(first)
    print(len(res))
    
    
main()

k, n = [int(x) for x in input().strip().split()]
a = [int(x) for x in input().strip().split()]
b = [int(x) for x in input().strip().split()]
sb = set(b)
sm = [0] * k
for i in range(k):
    sm[i] = sm[i - 1] + a[i]

answers = set()
for i in range(k):
    beg = b[0] - sm[i]
    t = set([beg + sm[j] for j in range(k)])
    if len(sb - t) == 0:
        answers.add(beg)

print(len(answers))


import sys

def main():
    k, n = map(int,sys.stdin.readline().split())
    a = list(map(int,sys.stdin.readline().split()))
    b = list(map(int,sys.stdin.readline().split()))
    
    for i in range(1,k):
        a[i] = a[i-1]+a[i]

    c = set()
    for i in range(k):
        x = b[0]-a[i]
        u = {}
        for j in range(k):
            u[x+a[j]] = True
        flag = True
        for j in range(n):
            if b[j] not in u:
                flag = False
                break
        if flag:
            c.add(x)

    print(len(c))

main()

import sys

K, N = [int(x) for x in sys.stdin.readline().split()]
a_s = [int(x) for x in sys.stdin.readline().split()]
b_s = [int(x) for x in sys.stdin.readline().split()]

poss = set([])
start = 1
for b in b_s:
    locls = set([])
    for a in a_s:
        b -= a
        locls.add(b)
    if start == 1:
        poss = locls
        start = 0
    else:
        poss = set.intersection(poss, locls)

print(len(poss))


from itertools import accumulate
k, n = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
suma = list(accumulate(a))

def possible(s):
    target = set(b)
    for i in a:
        s+= i
        if s in target: target.remove(s)
    return not target

pos = set()
for i in range(k):
    ini = b[0]-suma[i]
    if possible(ini):
        pos.add(ini)
print(len(pos))

k,n = list(map(int,input().split()))
a = []
b = []
temp = input().split()
s = 0
for i in range(k):
    s += int(temp[i])
    a.append(s)
list.sort(a)
temp = input().split()
for i in range(n):
    b.append(int(temp[i]))
list.sort(b)
count = 0
visit = set()
for i in range(k-n+1):
    dif = b[0]-a[0]
    if dif not in visit:
        visit.add(dif)
        add = True
        index = 0
        for j in range(n):
            while index < len(a):
                if a[index] == b[j]-dif:
                    break
                elif a[index] > b[j]-dif:
                    add = False
                    break
                else:
                    index += 1
            if index >= len(a):
                add = False
                break
            if not add:
                break
        if add:
            count += 1
    a = a[1:]
print(count)


I = lambda: list(map(int, input().split()))
k, n = I()
a, b = list(I()), list(I())
s = 0
for i in range(k):
    s += a[i]
    a[i] = s
#print(a)
ans = [set() for x in range(n)]
for i, y in enumerate(b):
    ans[i] = [y-x for x in a]
#print(ans)
ans2 = set(ans[0])
#print(ans2)
for x in ans:
    ans2.intersection_update(x)
#print(ans2)
print(len(ans2))


import sys

def solve():
	k, n = list(map(int, sys.stdin.readline().split()))
	mks = list(map(int, sys.stdin.readline().split()))
	pts = list(map(int, sys.stdin.readline().split()))

	for i in range(1, k):
		mks[i] = mks[i-1] + mks[i]

	mks = sorted(mks)
	pts = sorted(pts)

	vals = set()

	for i in range(k - n + 1):
		cand = pts[0] - mks[i]
		j = 0
		off = 0
		while j < len(pts):
			while i + j + off < k and pts[j] - cand > mks[i + j + off]:
				off += 1
			if i + j + off < k and pts[j] - mks[i + j + off] == cand:
				j += 1
			else:
				break
		if j == len(pts):
			vals.add(cand)

	print(len(vals))

solve()

k, n = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
st = set()
zn = b[0]
sums = [a[0]]
for j in range(1, len(a)):
    sums.append(sums[-1] + a[j])
for j in sums:
    st.add(b[0] - j)
for i in b: # �� ��� ������
    tmp = set()
    for j in sums: #�����
        tmp.add(i - j)
        
    st = st.intersection(tmp)
    #print(st)
    if len(st) == 0:
        break
print(len(st))
        


"""
from time import sleep
n,k=[int(i) for i in input().split()]

inf=[None for i in range(10**5)]
ans=[0 for i in range(10**5)]
def howMany(i):
    if i-k+1<0:
        inf[i]=1
        return
    elif i==k-1:
        inf[i]=2
        return 
    else:
        inf[i]=(inf[i-1]+inf[i-k])%(10**9+7)

for i in range(10**5):
    howMany(i)
    ans[i]=ans[i-1]+inf[i]
for i in range(n):
    a,b=[int(i)-1 for i in input().split()]
    print(ans[:20])
    print((a-1) if a-1>=0 else 0)
    print(ans[b]-ans[(a-1) if a-1>=0 else 0])%(10**9+7)

#a={'WWWRRRR','RWWWRRR','RRWWWRR','RRRWWWR','RRRRWWW','RRRRRRR','WWWWWWR','WWWRWWW','RWWWWWW'}
#print(len(a))
"""
k,n=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[]
ans=0
test=set()
for i in a:
    c.append(i if c==[] else (c[-1]+i))

def howMany(a1):
    nonlocal ans
    #print(a1)
    for i in b:
        if not i in a1: return 
    if a1[0] in test:
        return 
    else: test.add(a1[0])
    #print(b[0]-a1[0])
    ans+=1

for i in c:
    howMany(list([b[0]-i+x for x in c]))
print(ans)














k,n = list(map(int,input().split()))
A = list(map(int,input().split()))
B = list(map(int, input().split()))
S = [0] * k
for i in range(k):
	if i == 0:
		S[0] = A[0]
	else:
		S[i] = S[i - 1] + A[i]
S.sort()
B.sort()
ans = set()
for i,s in enumerate(S):
	if i > 0 and S[i - 1] == s:
		continue
	t = B[0] - s
	if n > 1:
		j = i + 1
		flag = False
		for m,u in enumerate(B[1:]):
			while j < len(S):
				if u - S[j] == t:
					if m == n - 2:
						flag = True
					j += 1
					break
				else:
					j += 1
		if flag == True:
			ans.add(t)
	else:
		ans.add(t)
print(len(ans))





def read():
    return [int(x) for x in input().split()]

k, n = read()
a = read()
b = read()

c = []
for x in a:
    c.append((c[-1] if c else 0) + x)
c = set(c)

z = set()

s = 0
for x in a:
    s += x
    i = b[0] - s
    for y in b[1:]:
        if y - i not in c:
            break
    else:
        z.add(i)

print(len(z))


from sys import stdin, stdout

k, n = map(int, stdin.readline().split())
marks = list(map(int, stdin.readline().split()))
values = list(map(int, stdin.readline().split()))

cnt = [marks[0]]
for i in range(1, k):
    cnt.append(cnt[-1] + marks[i])

cnt.sort()
values.sort()
ans = set()

for i in range(k - n + 1):
    x = values[0] - cnt[i]
    
    pos = 1
    ind = i + 1
    label = 1
    
    while pos < n and ind < k:
        if cnt[ind] + x < values[pos]:
            ind += 1
        elif cnt[ind] + x == values[pos]:
            ind += 1
            pos += 1
        else:
            label = 0
            break
    
    if label and pos == n:
        ans.add(x)

stdout.write(str(len(ans)))

#!/usr/bin/env python3
from sys import stdin, stdout

def rint():
    return list(map(int, stdin.readline().split()))
#lines = stdin.readlines()

k, n = rint()

a = list(rint())
b = list(rint())

for i in range(1,k):
    a[i] = a[i] + a[i-1]

a0 = min(a)
for i in range(len(a)):
    a[i] -= a0
a = set(a)

b0 = min(b)
for i in range(n):
    b[i] -= b0

ans = 0
for aa in a:
    diff = aa
    ans +=1
    for bb in b:
        if bb + diff in a:
            pass
        else:
            ans -= 1
            break

print(ans)





def read():
    return [int(x) for x in input().split()]


k,n = read()
a = read()
b = read()

sum = set()
tmp =[0]
for e in a:
    tmp.append(tmp[-1]+e)
    sum.add(tmp[-1])

ans = set()
for e in tmp[1:]:
    init = b[0]-e
    for bb in b[1:]:
        if bb - init not in sum:
            break
    else:
        ans.add(init)

print(len(ans))

def read():
    return [int(x) for x in input().split()]

k, n = read()
a = read()
b = read()

c = []
for x in a:
    c.append((c[-1] if c else 0) + x)
c = set(c)

z = set()

s = 0
for x in a:
    s += x
    i = b[0] - s
    for y in b[1:]:
        if y - i not in c:
            break
    else:
        z.add(i)

print(len(z))

o=lambda:[int(f)for f in input().split()]
k,n=o()
a=o()
b=o()
s=[]
for x in b:
    t=x
    t1=set()
    for y in a:
        t-=y
        t1.add(t)
    s+=[t1]
print(len(set.intersection(*s)))


R= lambda: map(int,input().split())
k,n=R()
a,b=list(R()),list(R())
c=[a[0]]
for i in range(1,k):
    c.append(c[-1]+a[i])
c=set(c)
s,cur=set(),0
for x in a:
    cur+=x
    new=b[0]-cur
    for y in b[1:]:
        if y-new not in c:
            break
    else:   s.add(new)
print(len(s))

k, n = list(map(int, input().split()))
j = list(map(int, input().split()))
b = list(map(int, input().split()))

b_set = set(b)
my_sum = [0 for i in range(k)]
my_sum[0] = j[0]

for i in range(1, k):
    my_sum[i] = my_sum[i - 1] + j[i]

pos_val = set()
for score in my_sum:
    pos_val.add(b[0] - score)

ans = 0
for start_val in pos_val:
    score_set = set()
    for marks in my_sum:
        score = start_val + marks
        score_set.add(score)

    if (score_set & b_set) == b_set:
        ans += 1

print(ans)


k, n = list(map(int,input().split()))
a = list(map(int,input().split()))
b = list(map(int,input().split()))
all_maybe_all_b = []
for mast_b in b:
    all_maybe_for_b_i=set()
    for slog in a:
        mast_b -= slog
        all_maybe_for_b_i.add(mast_b)
    all_maybe_all_b += [all_maybe_for_b_i]
pack_ans_intersection=set.intersection(*all_maybe_all_b)
#print(all_maybe_all_b)
#print(pack_ans_intersection)
print(len(pack_ans_intersection))


import sys

k, n = [int(i) for i in sys.stdin.readline().split()]
rate = [int(i) for i in sys.stdin.readline().split()]
rem = dict()
for i in sys.stdin.readline().split():
	v = int(i)
	if v in rem:
		rem[v] += 1
	else:
		rem[v] = 1
		
for i in range(len(rate)):
	if i > 0:
		rate[i] += rate[i-1]

ans = set()
ref = next(iter(rem));
for i in range(len(rate)):
	cnt = rem.copy()
	for j in range(len(rate)):
		v = ref + rate[j] - rate[i]
		if v in cnt:
			cnt[v] -= 1
			if cnt[v] == 0:
				del cnt[v]
	if len(cnt) == 0:
		ans.add(ref - rate[i])

print(len(ans))

(k, n) = (int(i) for i in input().split())

a = []
prev = 0
for i in input().split():
	prev =  prev+int(i)
	a.append(prev)

b = [int(i) for i in input().split()]
kands = set()
for i in a:
	kands.add(b[0]-i)
b = set(b)
cnt = 0
for i in kands:
	cur = set()
	for j in a:
		cur.add(i+j)	
	if b<=cur:
		cnt+=1
print(cnt)