Jury Marks

题意翻译

有 $k$ 个评委给一个 **初始分数未知的** 参赛者 **依次** 打分，其中第 $i$ 个评委会在第 $i$ 分钟内为参赛者打分，在第 $i$ 分钟结束时参赛者会 **立即** 获得 $a_i$ 的分数。 给出参赛者在某 $n$ 个 **正整分钟结束时** 的分数 $b_i$，问：这位参赛者可能有多少个 **数值不同的** 初始分数？ 输入格式： - 第 $1$ 行：输入 $k$，$n$ - 第 $2$ 行：输入 $k$ 个整数 $a_i$ - 第 $3$ 行：输入 $n$ 个整数 $b_i$ 输出格式： - 第 $1$ 行：输出 $1$ 个整数，表示答案 数据范围提示： $1 \leq n \leq k \leq 2 \times 10^3$，$- 2 \times 10^3 \leq a_i \leq 2 \times 10^3$，$- 4 \times 10^6 \leq b_i \leq 4 \times 10^6$，保证 $b_i$ 互不相同，但不保证 $b_i$ 按时间顺序给出。

题目描述

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&lt;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.

输入输出格式

输入格式

The first line contains two integers $ k $ and $ n $ ( $ 1<=n<=k<=2000 $ ) — the number of jury members and the number of scores Polycarp remembers. The second line contains $ k $ integers $ a_{1},a_{2},...,a_{k} $ ( $ -2000<=a_{i}<=2000 $ ) — jury's marks in chronological order. The third line contains $ n $ distinct integers $ b_{1},b_{2},...,b_{n} $ ( $ -4000000<=b_{j}<=4000000 $ ) — the values of points Polycarp remembers. Note that these values are not necessarily given in chronological order.

输出格式

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

输入输出样例

输入样例 #1

4 1
-5 5 0 20
10

输出样例 #1

3

输入样例 #2

2 2
-2000 -2000
3998000 4000000

输出样例 #2

1

说明

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 $ 4002000 $ .