你有一架天平和 $N$ 个砝码，这 $N$ 个砝码重量依次是 $W_1,W_2,···,W_N$。

请你计算一共可以称出多少种不同的正整数重量？

注意砝码可以放在天平两边。

输入格式

输入的第一行包含一个整数 $N$。

第二行包含 $N$ 个整数：$W_1,W_2,W_3,···,W_N$。

输出格式

输出一个整数代表答案。

数据范围

对于 $50%$ 的评测用例，$1≤N≤15$。
对于所有评测用例，$1≤N≤100$，$N$ 个砝码总重不超过 $10^5$。

输入样例：

3
1 4 6

输出样例：

10

样例解释

能称出的 1010 种重量是：$1、2、3、4、5、6、7、9、10、11$。

1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
4 = 4；
5 = 6 − 1；
6 = 6；
7 = 1 + 6；
9 = 4 + 6 − 1；
10 = 4 + 6；
11 = 1 + 4 + 6。

分析：

这里套用了母函数的模板，没有用dp方法做
这个题和hdu-1709一题是一样的，可以参考这个题的做法

#include <bits/stdc++.h>
using namespace std;
const int N=1050,M = 1000005;
int c1[M],c2[M],w[N];
int main(){
    int n;
    scanf("%d",&n);
    int maxl=0;
    for(int i=0;i<n;i++) {
        scanf("%d",&w[i]);
        maxl+=w[i];
    }
    c1[0]=1;c1[w[0]]=1;
    for(int i=1;i<n;i++){
        for(int j=0;j<=maxl;j++){
            for(int k=0;k<=w[i];k+=w[i]){
                c2[j+k]+=c1[j];
                c2[abs(j-k)]+=c1[j];
            }
        }
        for(int j=0;j<=maxl;j++){
            c1[j]=c2[j];
            c2[j]=0;
        }
    }
    int cnt=0;
    for(int i=1;i<=maxl;i++){
        if(c1[i]) cnt++;
    }
    cout<<cnt;
}