English · Original
Chinese · Translation
Formal · Original
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).
[samples]
## 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.
Polycarp 观看了一档电视节目，其中 #cf_span[k] 名评委依次给一名参赛者打分，每次加上一定数量的分数（可能为负，即扣分）。参赛者初始有一定分数，随后每个评委的打分依次加到其分数上。已知第 #cf_span[i] 名评委给出了 #cf_span[ai] 分。
Polycarp 不记得参赛者在 #cf_span[k] 个打分开始前的初始分数，但他记得在每个评委打分后公布的分数中，有 #cf_span[n]（#cf_span[n ≤ k]）个值为 #cf_span[b1, b2, ..., bn]（保证所有 #cf_span[bj] 互不相同）。Polycarp 可能没有记住所有公布的分数，即 #cf_span[n < k]。注意，初始分数并未被公布。
你的任务是确定参赛者在评委打分前可能的初始分数有多少种选项。
第一行包含两个整数 #cf_span[k] 和 #cf_span[n]（#cf_span[1 ≤ n ≤ k ≤ 2 000]）——评委人数和 Polycarp 记住的分数个数。
第二行包含 #cf_span[k] 个整数 #cf_span[a1, a2, ..., ak]（#cf_span[ - 2 000 ≤ ai ≤ 2 000]）——评委按时间顺序给出的分数。
第三行包含 #cf_span[n] 个*互不相同*的整数 #cf_span[b1, b2, ..., bn]（#cf_span[ - 4 000 000 ≤ bj ≤ 4 000 000]）——Polycarp 记住的分数值。注意这些值不一定按时间顺序给出。
请输出参赛者在评委打分前可能的初始分数的选项数量。如果 Polycarp 记忆有误，不存在任何可能选项，请输出 "_0_"（不含引号）。
第一个示例的答案为 #cf_span[3]，因为参赛者初始可能有 #cf_span[ - 10]、#cf_span[10] 或 #cf_span[15] 分。
在第二个示例中，只有一个正确的初始分数，等于 #cf_span[4 002 000]。
## Input
第一行包含两个整数 #cf_span[k] 和 #cf_span[n]（#cf_span[1 ≤ n ≤ k ≤ 2 000]）——评委人数和 Polycarp 记住的分数个数。第二行包含 #cf_span[k] 个整数 #cf_span[a1, a2, ..., ak]（#cf_span[ - 2 000 ≤ ai ≤ 2 000]）——评委按时间顺序给出的分数。第三行包含 #cf_span[n] 个*互不相同*的整数 #cf_span[b1, b2, ..., bn]（#cf_span[ - 4 000 000 ≤ bj ≤ 4 000 000]）——Polycarp 记住的分数值。注意这些值不一定按时间顺序给出。
## Output
请输出参赛者在评委打分前可能的初始分数的选项数量。如果 Polycarp 记忆有误，不存在任何可能选项，请输出 "_0_"（不含引号）。
[samples]
## Note
第一个示例的答案为 #cf_span[3]，因为参赛者初始可能有 #cf_span[ - 10]、#cf_span[10] 或 #cf_span[15] 分。在第二个示例中，只有一个正确的初始分数，等于 #cf_span[4 002 000]。
**Definitions**
Let $ k, n \in \mathbb{Z} $ with $ 1 \leq n \leq k \leq 2000 $.
Let $ A = (a_1, a_2, \dots, a_k) \in \mathbb{Z}^k $ be the sequence of jury marks.
Let $ B = \{b_1, b_2, \dots, b_n\} \subset \mathbb{Z} $ be the set of remembered scores (all distinct).
Define the prefix sum sequence $ S = (s_0, s_1, \dots, s_k) $, where:
$$
s_0 = x, \quad s_i = x + \sum_{j=1}^i a_j \quad \text{for } i = 1, \dots, k,
$$
and $ x \in \mathbb{Z} $ is the unknown initial score.
Let $ P = \{s_1, s_2, \dots, s_k\} $ be the set of scores announced after each jury member’s rating.
**Constraints**
1. $ B \subseteq P $ — all remembered scores must appear among the announced scores.
2. $ |B| = n $, $ |P| = k $, and $ B \subset P \subseteq \mathbb{Z} $.
**Objective**
Find the number of integer values $ x \in \mathbb{Z} $ such that $ B \subseteq \left\{ x + \sum_{j=1}^i a_j \mid i = 1, \dots, k \right\} $.
API Response (JSON)
{
"problem": {
"name": "C. Jury Marks",
"description": {
"content": "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 s",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF831C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 s...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Polycarp 观看了一档电视节目，其中 #cf_span[k] 名评委依次给一名参赛者打分，每次加上一定数量的分数（可能为负，即扣分）。参赛者初始有一定分数，随后每个评委的打分依次加到其分数上。已知第 #cf_span[i] 名评委给出了 #cf_span[ai] 分。\n\nPolycarp 不记得参赛者在 #cf_span[k] 个打分开始前的初始分数，但他记得在每个评委打分后公布的分数中，有...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ k, n \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq k \\leq 2000 $. \nLet $ A = (a_1, a_2, \\dots, a_k) \\in \\mathbb{Z}^k $ be the sequence of jury marks. \nLet $ B = \\{b_1, b_2, \\dots, b_...",
"is_translate": false,
"language": "Formal"
}
]
}