#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

struct vec3 {
    ll x;
    ll y;
    ll z;
};

ll S[20][1LL << 18];

ll cost(vec3 from, vec3 to) {
    ll ret = abs(to.x - from.x) + abs(to.y - from.y) + std::max(0LL, to.z - from.z);
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    vector<vec3> v(N);
    REP(i, N) {
        cin >> v[i].x >> v[i].y >> v[i].z;
    }

    ll p = pow(2LL, N);
    REP(i, N) {
        REP(j, p) {
            S[i][j] = INF;
        }
    }

    S[0][1] = 0;
    REP(i, p) {
        REP(j, N) {
            if (((i >> j) & 1) == 0)
                continue;

            ll b = (i & (~(1LL << j)));
            REP(k, N) {
                if (((b >> k) & 1) == 0)
                    continue;
                ll cst = cost(v[k], v[j]) + S[k][b];
                S[j][i] = std::min(S[j][i], cst);
            }
        }
    }

    ll ans = INF;
    REP(i, N) {
        ans = std::min(ans, S[i][p - 1] + cost(v[i], v[0]));
    }
    cout << ans << endl;

    return 0;
}
#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
using namespace std;

//#define DEBUG
#ifdef DEBUG
template<typename ...Args>
int debug(const Args &...args){
	return fprintf(stderr,args...);
}
#else
#define debug(...) void()
#endif

typedef unsigned long long ull;
typedef unsigned uint;
typedef long long ll;
#define G getchar()
int read()
{
	int x=0; bool flg=false; char ch=G;
	for (;!isdigit(ch);ch=G) if (ch=='-') flg=true;
	for (;isdigit(ch);ch=G) x=(x<<3)+(x<<1)+(ch^48);
	return flg?-x:x;
}
#undef G
#define fi first
#define se second

const int mod=998244353;
inline int upd(const int &x){return x+(x>>31&mod);}
inline void add(int &x,const int &y){x=upd(x+y-mod);}
inline void iadd(int &x,const int &y){x=upd(x-y);}
int qpow(int x,int y){
	int res=1;
	for (;y;y>>=1,x=1LL*x*x%mod)
		if (y&1) res=1LL*res*x%mod;
	return res;
}

//typedef pair<int,int> P;
#define rep(i,l,r) for (int i(l),_##i(r);i<=_##i;i++)
#define per(i,l,r) for (int i(r),_##i(l);i>=_##i;i--)
#define all(x) (x).begin(),(x).end()
#define forall(x,y) for (const int &y: e[x])

int n,w[110];
int dp[110][10010];

void solve(){
	n=read(); int S=0;
	rep(i,1,n) w[i]=read(),S+=w[i];
	if (S&1) return puts("0"),void();
	auto F=dp;
	F[0][0]=1;
	rep(_,1,n){
		const int &W=w[_];
		per(i,0,n){
			rep(j,0,n*100){
				if (i<n&&j+W<=n*100);
				else continue;
				add(F[i+1][j+W],F[i][j]);
			}
		}
	}
	static int fac[110];
	fac[0]=1; rep(i,1,n) fac[i]=1LL*fac[i-1]*i%mod;
	int z=0;
	rep(i,0,n) add(z,1LL*F[i][S>>1]*fac[i]%mod*fac[n-i]%mod);
	printf("%d\n",z);
}

int main()
{
	for (int T=1;T--;) solve();
	return 0;
}