Problem: Beakers of various capacities are given. First, choose one of the largest beakers and pour it through the faucet until it is full. Next, transfer the water from the beaker to another beaker according to the following rules.

* All water in the beaker must be transferred to another beaker without leaving. However, if it is not possible to transfer all the water to one beaker, it may be divided into multiple beakers.
* When you fill the beaker with water, you must pour water until it is full. Also, do not spill water.
* Do not pour water from multiple beakers into the same beaker at once.
* Only water the same beaker once.

<image>



When following this rule, create a program that inputs the number of beakers n and the capacity of each beaker, determines whether water can be poured into all beakers, and outputs it. Output YES (half-width uppercase letters) when water can be poured into all beakers, and NO (half-width uppercase letters) when water cannot be poured.



Input

A sequence of multiple datasets is given as input. The end of the input is indicated by a single line of zeros. Each dataset is given in the following format:


n
c1 c2 ... cn


The number of beakers n (1 ≤ n ≤ 50) is given on the first line. The second line is given the integer ci (1 ≤ ci ≤ 100), which represents the capacity of the i-th beaker.

The number of datasets does not exceed 105.

Output

The judgment result is output to one line for each data set.

Example

Input

10
11 2 23 4 2 12 8 5 2 10
8
2 1 3 11 2 3 1 4
9
5 9 1 2 4 8 17 1 8
8
3 38 9 4 18 14 19 5
1
1
0


Output

YES
YES
YES
NO
YES

Solution (in CPP):

Solution:

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <memory>
#include <string>

#include <algorithm>
#include <complex>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <bitset>

using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
#define strtok_r strtok_s
#endif

#define ITER(c)             __typeof__((c).begin())
#define FOREACH(it, c)      for (ITER(c) it=(c).begin(); it != (c).end(); ++it)
#define RITER(c)            __typeof__((c).rbegin())
#define RFOREACH(it, c)     for (RITER(c) it=(c).rbegin(); it != (c).rend(); ++it)
#define REP(i, n)           REPEAT(i, 0, n)
#define RREP(i, n)          RREPEAT(i, 0, n)
#define REPEAT(i, k, n)     for(int i = (k); i < ((k)+(n)); ++i)
#define RREPEAT(i, k, n)    for(int i = (k)+(n)-1; i >= (k); --i)
#define FROMTO(i,f,t)       for(int i = f; i < t; i++)
#define ALL(c)              (c).begin(), (c).end()
#define LLPOW(p1,p2)        ((ll)pow((double)(p1), (int)p2))
#define ESIZEOF(A)          (sizeof(A)/sizeof((A)[0]))
#define CIN_NO_SYNC         do { cin.tie(0); ios_base::sync_with_stdio(false); } while(0)
#define GETSTR(p)           fgets((p), sizeof(p), stdin)
#define CHOMP(p)            do{ char *_q = (p) + strlen(p)-1; if(*_q == '\n' || *_q == '\r') *_q = 0; } while(0)
#define FILL(m,v)           memset(m, v, sizeof(m))
#define mp                  make_pair
#define pb                  push_back
template<class _T> _T MAX(_T p1,_T p2){return (p1>p2)?p1:p2;} 
template<class _T> _T MIN(_T p1,_T p2){return (p1<p2)?p1:p2;} 
template <class _Tv> inline string join(const _Tv &v,string sep=" "){
    ostringstream s;FOREACH(it,v){if(it!=v.begin())s<<sep;s<<*it;};return s.str();
}

typedef long long ll;
typedef unsigned long long ull;
typedef double D;
typedef complex<D> P;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define X real()
#define Y imag()
#define EPS (1e-9)
#define DEQ(p1,p2) (abs((p1)-(p2)) < EPS)

#ifdef _DEBUG
template<class _Tv> inline void _prfe(const char *_n,const _Tv _c,bool _p=false){
    ITER(_c) _it=_c.begin();
    if(_p){cout<<_n<<" = ["<<endl;for(;_it!=_c.end();++_it)cout<<"    "<<*_it<<endl;cout<<"]"<<endl; }
    else{cout<<_n<<" = [ ";if(_c.size()){cout<<*_it++;for(;_it!=_c.end();++_it)cout<<", "<<*_it;}cout<<" ]"<<endl; }
}
ostream &operator<<(ostream &os, const pair<int,int> &p){return(os<<"("<<p.first<<","<<p.second<<")");}
#define pf printf
#define pr(n) do{cout<<#n" = "<<(n)<<endl;}while(0)
#define prfe(n) _prfe(#n, n)
#define prfep(n) _prfe(#n, n, true)
#define dbgchk(n) do{if(n)throw;}while(0)
#else
#define pf(...) /* */
#define pr(...) /* */
#define prfe(...) /* */
#define prfep(...) /* */
#define dbgchk(...) /* */
#endif

int n;
int b[101], f[101];
enum { EMPTY=0,FULL=1,USED=2 };

void dbg(){
    pf("f = "); REP(i,n) pf("%2d, ", f[i]); pf("\n");
}

bool move(int i, int v, int n_empty);
bool rec(int n_empty){
    if(n_empty == 0) return true;
    REP(i,n){
        if(f[i] == EMPTY) break;
        if(f[i] == FULL){
            f[i] = USED; dbg();
            if(move(i+1, b[i], n_empty)) return true;
            f[i] = FULL; dbg();
        }
    }
    return false;
}
bool move(int i, int v, int n_empty){
    if(v == 0) return rec(n_empty);
    FROMTO(j, i, n){
        if(f[j] != EMPTY) continue;
        if(v < b[j]) continue;
        f[j] = FULL; dbg();
        if(move(j+1, v-b[j], n_empty-1)) return true;
        if(i == j && f[j] == EMPTY) break;
        f[j] = EMPTY; dbg();
    }
    return false;
}

bool solve(){
    sort(b, b+n, greater<int>());
    pf("b = "); REP(i,n) pf("%2d, ", b[i]); pf("\n");
    REP(i,n) f[i] = EMPTY;
    f[0] = FULL; dbg();
    return rec(n-1);
}

int main(){
    while(cin >> n && n){
        REP(i,n) cin >> b[i];
        cout << (solve()?"YES":"NO") << endl;
    }
    return 0;
}