CSU-ACM2017暑期训练1-Debug与STL B - Jury Marks

B - Jury Marks

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 ai 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 b1, b2, ..., bn (it is guaranteed that all values bj 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 a1, a2, ..., ak ( - 2 000 ≤ ai ≤ 2 000) — jury's marks in chronological order.

The third line contains n distinct integers b1, b2, ..., bn ( - 4 000 000 ≤ bj ≤ 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).
           

Example

Input

4 1
-5 5 0 20
10

Output

3



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.
           

这题就是要枚举出所有可能的初始分数 initVal 。

要点有：前缀和、去重复、二分搜索。

程序用两个数组 a[] 和 b[] 分别保存评委打分情况的前缀和，以及Polycarp记得的某些阶段的分数。

随着输入的进行而建立的前缀和 a[] 中的值有无序性，所以可以对其进行排序，从而使后续的程序中可以使用二分搜索，进而提高运行效率。

为了得到 initVal 的可能达到的最大数量，需要枚举出所有有效 的 initVal 。

由于 a[] 表示了前缀和，所以任取 b[] 中的一个元素（如 b[0]），枚举它与所有前缀和的差，即可得到所有可能的 initVal ：

initVali=b[0]−a[i]

算出 initVal 有效性的关键在于枚举 b[] 中的每一个元素 b[j]，看它们是否有相应的 a[] 中的元素 a[x] (a[x]是不确定的，通过二分搜索来查找它)和它们进行运算，得出 initVal 。具体公式如下：

b[j]−initVal=a[x]

如果所有 b[j] 都可以满足上述公式，就说明所取的 initVal 是有效的。将它加入set，进行下一次判断。

显然， a[] 中的元素的不同决定了不同的 initVal 。但是，可能存在 a[x] == a[y] 的情况，从而导致重复的 initVal 出现。不过 initVal 的重复不会影响结果，因为最终得到的有效 initVal 放入了set，而set确保了其中每个元素的独立性。所以程序只需输出set的大小就可以得到所求答案了。

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
set<int> mySet;
int a[], b[];
int main()
{
    int k, n;
    while (cin >> k >> n) {
        mySet.clear();
        cin >> a[];
        for(int i = ; i < k; i++){ //生成前缀和。
            cin >> a[i];
            a[i] += a[i - ];
        }
        for(int i = ; i < n; i++){
            cin >> b[i];
        }
        sort(b, b + n);
        sort(a, a + k);
        //对a[]排序，重复的前缀和对计算影响不大，只是重复计算几次，对存放在set中的结果没有影响。

        for(int i = ; i < k; i++){     
            int initVal = b[] - a[i];
            //任意取b[]中的元素作为计算基础，这里取b[0]。

            int possible = ;
            //对b[]中的每一个元素进行判断，看是否有一个a[x]（x不定）满足initVal - b[j] == a[x]。

                possible += binary_search(a, a + k, b[j] - initVal);
                //对前缀和的排序使得程序适用二分搜索，提高效率。

            }
            if(possible == n)           
            //如果b[]中的元素全部匹配某个initVal，说明这个initVal是一种可能的初始值。
                 mySet.insert(initVal);  
                 //将这个初始值放入set中。即使前面没有对前缀和去重，得到的重复initVal也在set中自动去重了。
        }
        cout << mySet.size() << endl;   //由前文可知，set的大小就是所有可能的initVal数量。
    }
    return ;
}