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.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Complete search

Constructive algorithms


Solutions:
def solve():
	(k, n) = get([int])
	A = get([int])
	B = get([int])
	Bset = set(B)
	s = list(itertools.accumulate(A))
	valid = set()
	count = 0
	for (judge, current) in itertools.product(B[:1], s):
		score = judge - current
		s2 = set((score + i for i in s))
		if Bset <= s2:
			valid.add(score)
	return len(valid)
_testcases = '\n4 1\n-5 5 0 20\n10\n\n3\n\n\n2 2\n-2000 -2000\n3998000 4000000\n\n1\n'.strip()
import re
import sys
import math
import heapq
from heapq import heapify, heappop, heappush
import bisect
from bisect import bisect_left, bisect_right
import operator
from operator import itemgetter, attrgetter
import itertools
import collections
inf = float('inf')
sys.setrecursionlimit(10000)

def tree():
	return collections.defaultdict(tree)

def cache(func):
	cache_dict = {}

	def _cached_func(*args, _get_cache=False):
		if _get_cache:
			return cache_dict
		if args in cache_dict:
			return cache_dict[args]
		cache_dict[args] = func(*args)
		return cache_dict[args]
	return _cached_func

def equal(x, y, epsilon=1e-06):
	if -epsilon <= x - y <= epsilon:
		return True
	if -epsilon <= x <= epsilon or -epsilon <= y <= epsilon:
		return False
	return -epsilon <= (x - y) / x <= epsilon or -epsilon <= (x - y) / y <= epsilon

def get(_type):
	if type(_type) == list:
		if len(_type) == 1:
			_type = _type[0]
			return list(map(_type, input().strip().split()))
		else:
			return [_type[i](inp) for (i, inp) in enumerate(input().strip().split())]
	else:
		return _type(input().strip())
print(solve())


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))


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):
		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()


def init():
	inp = input().split()
	k = int(inp[0])
	n = int(inp[1])
	va = [int(i) for i in input().split()]
	vb = [int(i) for i in input().split()]
	return (va, vb)

def pross(va, vb):
	acc = 0
	for (i, a) in enumerate(va):
		acc += a
		va[i] = acc
	vals = [set() for _ in range(len(vb))]
	for (i, b) in enumerate(vb):
		for a in va:
			vals[i].add(b - a)
	return vals

def solve(vals):
	ans = set()
	for (i, v) in enumerate(vals[0]):
		for s in vals[1:]:
			if v not in s:
				break
		else:
			ans.add(v)
	return len(ans)
print(solve(pross(*init())))


from copy import copy
(k, n) = list(map(int, input().split()))
temp = list(map(int, input().split()))
l = list(map(int, input().split()))
t = [temp[0]]
s = temp[0]
for i in range(1, k):
	s += temp[i]
	t.append(s)
temp = t
temp.sort()
l.sort()
i = 0
while i < k - 1:
	if temp[i] == temp[i + 1]:
		del temp[i]
		k -= 1
		i -= 1
	i += 1

def f(index):
	global add
	add = l[0] - temp[index]
	cop = copy(temp)
	for i in range(k):
		cop[i] += add
	found = 0
	for i in range(index, k):
		if found + 1 == n:
			return True
		if cop[i] == l[found + 1]:
			found += 1
	if found + 1 == n:
		return True
	return False
out = 0
for i in range(0, k - n + 1):
	if f(i):
		out += 1
print(out)


(k, n) = map(int, input().split())
scores = [int(x) for x in input().split()]
remembered = [int(x) for x in input().split()]
temp = 0
possibility = []
for x in scores:
	temp += x
	if -1 * temp not in possibility:
		possibility.append(-1 * temp)
lol = []
for x in remembered:
	temp = []
	for y in possibility:
		temp.append(x + y)
	lol.append(temp)
out = lol[0]
for x in range(1, len(lol)):
	out = list(set(lol[x]).intersection(out))
print(len(out))


import sys
rline = lambda : sys.stdin.readline()

def secondScore(alst, i, num):
	if i == 1:
		return num
	return secondScore(alst, i - 1, num - alst[i - 1])

def annSet(score, alst, i):
	ans = {score}
	x = score
	y = score
	for j in range(i - 1, 0, -1):
		x -= alst[j]
		ans.add(x)
	for j in range(i, len(alst)):
		y += alst[j]
		ans.add(y)
	return ans

def CF831C(alst, blst):
	if len(blst) > len(alst):
		return 0
	if len(alst) == 1:
		return 1 if len(blst) == 1 else 0
	ssSet = set()
	x = blst[0]
	bset = set(blst)
	for i in range(1, len(alst) + 1):
		scoreSet = annSet(x, alst, i)
		works = True
		for b in bset:
			if b not in scoreSet:
				works = False
				break
		if works:
			ssSet.add(min(scoreSet))
	return len(ssSet)
rline()
alst = [int(i) for i in rline().split()]
blst = [int(i) for i in rline().split()]
print(CF831C(alst, blst))


(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)


from collections import defaultdict
(k, n) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
d = defaultdict(int)
for i in range(n):
	d[b[i]] = i
s = set()
diff = 0
for ai in a:
	diff += ai
	s.add(b[0] - diff)
ans = 0
for si in s:
	flag = [False] * n
	x = si
	for ai in a:
		x += ai
		if x in d:
			flag[d[x]] = True
	if flag == [True] * n:
		ans += 1
print(ans)


(k, n) = 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)
	if len(st) == 0:
		break
print(len(st))


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()))
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))


(k, n) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = set()
sums = [0]
for i in range(k):
	sums.append(sums[-1] + a[i])
sums.pop(0)
for i in range(k):
	x.add(b[0] - sums[i])
count = 0
for s in x:
	points = []
	for i in range(k):
		points.append(s + sums[i])
	temp = b.copy()
	points.sort()
	temp.sort()
	for num in points:
		if num == temp[0]:
			temp.pop(0)
			if temp == []:
				break
		if num > temp[0]:
			break
	if temp == []:
		count += 1
print(count)


(k, n) = 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)


s = input().split(' ')
k = int(s[0])
n = int(s[1])
arr = []
sum_arr = []
s = input().split(' ')
for i in range(k):
	arr.append(int(s[i]))
	sum_arr.append(arr[-1])
	if i >= 1:
		sum_arr[i] += sum_arr[i - 1]
arr_2 = []
s = input().split(' ')
for i in range(n):
	arr_2.append(int(s[i]))
possible_intial = set()
for i in sum_arr:
	possible_intial.add(arr_2[0] - i)
arr_2 = set(arr_2)
ctr = 0
for i in possible_intial:
	after_values = set()
	for j in sum_arr:
		after_values.add(i + j)
	flag = 0
	for j in arr_2:
		if j not in after_values:
			flag = 1
			break
	if flag == 0:
		ctr += 1
print(ctr)


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 typing import List, Set

def possible_initials(associative_marks: List[int], heard: int) -> Set[int]:
	return {heard - mark for mark in associative_marks}

def associative_mark(marks: List[int]) -> List[int]:
	return list(map(sum, [marks[:i + 1] for i in range(len(marks))]))

def get_list_integer():
	return list(map(int, input().strip().split()))

def initial_score_options(marks: List[int], heard: List[int]) -> int:
	associative_marks = associative_mark(marks)
	initial_set = possible_initials(associative_marks, heard[0])
	for h in heard[1:]:
		initial_set &= possible_initials(associative_marks, h)
	return len(initial_set)

def main():
	_ = input()
	marks = get_list_integer()
	heard = get_list_integer()
	print(initial_score_options(marks, heard))
main()


(mark_num, remember_num) = [int(i) for i in input().split()]
marks = [int(i) for i in input().split()]
after_scores = {int(i) for i in input().split()}
assert mark_num == len(marks) and len(after_scores) == remember_num
template = []
score = 0
for m in marks:
	score += m
	template.append(score)
poss_starts = set()
random_score = next(iter(after_scores))
for t in template:
	poss_starts.add(random_score - t)
valid_starts = 0
for s in poss_starts:
	score = s
	resulting_scores = set()
	for m in marks:
		score += m
		resulting_scores.add(score)
	if after_scores.issubset(resulting_scores):
		valid_starts += 1
print(valid_starts)


from sys import stdin
input = lambda : stdin.readline().strip()
(k, n) = map(int, input().split())
a = [*map(int, input().split())]
b = sorted([*map(int, input().split())])
c = [0 for i in range(k)]
c[0] = a[0]
for i in range(1, k):
	c[i] = c[i - 1] + a[i]
c.sort()
if n == 1:
	print(len(set(c)))
	exit()
start_vals = set()
min_diff = b[-1] - b[0]
max_base = c[-1]
d = [b[i + 1] - b[i] for i in range(n - 1)]
discarded = set()
for i in range(k):
	bval = b[0] - c[i]
	if max_base - c[i] < min_diff or bval in start_vals or i + n > k or (bval in discarded):
		break
	start = c[i]
	di = 0
	curr = c[i] + d[di]
	for j in range(i + 1, k):
		if curr == c[j]:
			di += 1
			if di == n - 1:
				start_vals.add(b[0] - start)
				break
			curr += d[di]
print(len(start_vals))


from sys import stdin, stdout

def rint():
	return list(map(int, stdin.readline().split()))
(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 list_input():
	return list(map(int, input().split()))

def map_input():
	return map(int, input().split())

def map_string():
	return input().split()
(n, k) = map_input()
a = list_input()
b = list_input()
pos = set()
pref = []
cur = 0
for i in a:
	cur += i
	pref.append(cur)
for j in pref:
	pos.add(b[0] - j)
ans = 0
for i in pos:
	s = set(b)
	for j in pref:
		s.discard(i + j)
	if len(s) == 0:
		ans += 1
print(ans)


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
A = list(map(int, input().split()))
B = sorted(list(set(list(map(int, input().split())))))
for i in range(1, len(B)):
	B[i] -= B[0]
B[0] = 0
cur = 0
A_s = set()
for x in A:
	cur += x
	A_s.add(cur)
A = sorted(list(A_s))
ans = 0
for (i, delta) in enumerate(A):
	f = i
	s = 0
	while f < len(A) and s < len(B):
		if B[s] + delta == A[f]:
			s += 1
		f += 1
	if s == len(B):
		ans += 1
print(ans)


f = lambda : list(map(int, input().split()))
(k, n) = f()
(a, b) = (f(), f())
for i in range(k - 1):
	a[i + 1] += a[i]
t = []
for x in b:
	t.append(set((x - y for y in a)))
print(len(set.intersection(*t)))


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)


(n, k) = (int(x) for x in input().split())
n += 1
scores = [0]
for diff in input().split():
	scores.append(scores[-1] + int(diff))
idxs = sorted(range(n), key=lambda x: scores[x])
rems = sorted((int(x) for x in input().split()))
ans = set()
for base in range(n):
	if idxs[base] == 0:
		continue
	i = 1
	for idx in idxs[base + 1:]:
		if i == k:
			break
		if idx != 0 and scores[idx] - scores[idxs[base]] == rems[i] - rems[0]:
			i += 1
	if i == k:
		ans.add(rems[0] - scores[idxs[base]])
print(len(ans))


(n, m) = map(int, input().split())
arr = [int(x) for x in input().split()]
dist = [int(x) for x in input().split()]
for i in range(1, n):
	arr[i] = arr[i] + arr[i - 1]
lis = []
for i in range(m):
	val = dist[i]
	s = set()
	for j in range(n):
		s.add(val - arr[j])
	lis.append(s)
print(len(set.intersection(*lis)))


(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()]
dic = dict()
for i in B:
	if i not in dic:
		dic[i] = 1
pref = [0] * len(A)
pref[0] = A[0]
for i in range(1, k):
	pref[i] = A[i] + pref[i - 1]
ans = set()
for i in range(k):
	x = B[0] - pref[i]
	c = 0
	ok = 0
	for j in range(k):
		if pref[j] + x in dic and dic[pref[j] + x] == 1:
			dic[pref[j] + x] = 2
			ok += 1
	for j in range(k):
		if pref[j] + x in dic and dic[pref[j] + x] == 2:
			dic[pref[j] + x] = 1
	if ok == n:
		ans.add(x)
print(len(ans))


import sys
fin = sys.stdin
fout = sys.stdout
(k, n) = list(map(int, fin.readline().split()))
a = list(map(int, fin.readline().split()))
b = list(map(int, fin.readline().split()))
b.sort()
for i in range(1, k):
	a[i] += a[i - 1]
a = sorted(set(a))
cnt = 0
set_b = set(b)
for i in range(len(a) - len(b) + 1):
	x = b[0] - a[i]
	set_grades = set()
	for j in range(i, len(a)):
		set_grades.add(x + a[j])
	if len(set_b.intersection(set_grades)) == len(set_b):
		cnt += 1
fout.write(str(cnt))
fout.close()


(n, k) = map(int, input().split())
jury = []
remember = []
ans = []
for i in list(map(int, input().split())):
	jury.append(i)
for i in list(map(int, input().split())):
	remember.append(i)
juryPrefix = len(jury) * [jury[0]]
for i in range(1, len(jury)):
	juryPrefix[i] = jury[i] + juryPrefix[i - 1]
for i in range(len(remember)):
	s = set()
	for j in range(len(juryPrefix)):
		s.add(remember[i] - juryPrefix[j])
	ans.append(s)
print(len(set.intersection(*ans)))


import sys
inp = [int(x) for x in sys.stdin.read().split()]
ii = 0
k = inp[ii]
ii += 1
n = inp[ii]
ii += 1
marks = inp[ii:ii + k]
ii += k
scores = inp[ii:ii + n]
pre = [0]
for x in marks:
	pre.append(pre[-1] + x)
ans = set()
for b in pre[1:]:
	ans.add(scores[0] - b)
for a in scores[1:]:
	scset = set()
	for b in pre[1:]:
		scset.add(a - b)
	ans = ans & scset
print(len(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(len(pack_ans_intersection))


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)))


(k, n) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
alls = []
for m in b:
	al = set()
	for s in a:
		m -= s
		al.add(m)
	alls += [al]
p = set.intersection(*alls)
print(len(p))


(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
	for i in b:
		if not i in a1:
			return
	if a1[0] in test:
		return
	else:
		test.add(a1[0])
	ans += 1
for i in c:
	howMany(list([b[0] - i + x for x in c]))
print(ans)


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
ans = [set() for x in range(n)]
for (i, y) in enumerate(b):
	ans[i] = [y - x for x in a]
ans2 = set(ans[0])
for x in ans:
	ans2.intersection_update(x)
print(len(ans2))


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))


(n, k) = [int(x) for x in input().split()]
marks = [int(x) for x in input().split()]
scores = set([int(x) for x in input().split()])
possible = set()
for i in [min(scores) - sum(marks[:i + 1]) for i in range(len(marks))]:
	j = i
	values = set()
	for mark in marks:
		j += mark
		values.add(j)
	if scores <= values:
		possible.add(i)
print(len(possible))


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(k, n) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
d = defaultdict(int)
for i in range(n):
	d[b[i]] = i
s = set()
diff = 0
for ai in a:
	diff += ai
	s.add(b[0] - diff)
ans = 0
for si in s:
	flag = [False] * n
	x = si
	for ai in a:
		x += ai
		if x in d:
			flag[d[x]] = True
	if flag == [True] * n:
		ans += 1
print(ans)


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()


(n, k) = map(int, input().strip().split())
t = input()
a = list(map(int, t.strip().split()))
t = input()
b = list(map(int, t.strip().split()))
sum = []
ans = {}
for i in range(n):
	if i == 0:
		sum.append(a[0])
	else:
		sum.append(sum[i - 1] + a[i])
sum.sort()
vis = {}
i = 1
while i < n:
	if sum[i] == sum[i - 1]:
		vis[i] = 1
	i += 1
for i in range(k):
	for j in range(n):
		if vis.get(j):
			continue
		if ans.get(b[i] - sum[j]) == None:
			ans[b[i] - sum[j]] = 1
		else:
			ans[b[i] - sum[j]] += 1
cnt = 0
for i in ans:
	if ans[i] == k:
		cnt += 1
print(cnt)


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)))


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))


(n, k) = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
for i in range(1, n):
	A[i] += A[i - 1]
pos = []
for i in A:
	pos.append(B[0] - i)
pos = set(pos)
cnt = 0
b = set(B)
for p in pos:
	s = set()
	for u in A:
		s.add(u + p)
	if s.intersection(b) == b:
		cnt += 1
print(cnt)


import itertools
(n, m) = (int(x) for x in input().split())
marks = (int(x) for x in input().split())
scores = sorted((int(x) for x in input().split()))
marks = sorted(itertools.accumulate(marks))
ans = set()
for i in range(n):
	mark0 = marks[i]
	score0 = scores[0]
	score_it = iter(scores[1:])
	score = next(score_it, None)
	for mark in marks[i + 1:]:
		if score is None:
			break
		if mark - mark0 == score - score0:
			score = next(score_it, None)
	if score is None:
		ans.add(score0 - mark0)
print(len(ans))


f = lambda : list(map(int, input().split(' ')))
(k, n) = f()
(a, b) = (f(), f())
all = []
for m in b:
	al = set()
	for s in a:
		m -= s
		al.add(m)
	all += [al]
p = set.intersection(*all)
print(len(p))


(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))


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))


import copy
p = 0
t = {}
s = set()
(k, n) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
t[a[0]] = 1
for i in range(1, k):
	a[i] += a[i - 1]
	if a[i] in t:
		t[a[i]] += 1
	else:
		t[a[i]] = 1
for i in a:
	r = copy.copy(t)
	x = b[0] - i
	if x not in s:
		s.add(x)
		p += 1
		if n == 1:
			continue
		else:
			for j in range(1, n):
				if b[j] - x not in r:
					p -= 1
					break
				if r[b[j] - x] == 0:
					p -= 1
					break
				r[b[j] - x] -= 1
print(p)