Problem: Problem Statement

You are given a positive integer sequence $A$ of length $N$. You can remove any numbers from the sequence to make the sequence “friendly". A sequence is called friendly if there exists an integer $k$ (>1) such that every number in the sequence is a multiple of $k$. Since the empty sequence is friendly, it is guaranteed that you can make the initial sequence friendly.

You noticed that there may be multiple ways to make the sequence friendly. So you decide to maximize the sum of all the numbers in the friendly sequence. Please calculate the maximum sum of the all numbers in the friendly sequence which can be obtained from the initial sequence.

* * *

Input

The input consists of a single test case formatted as follows.

> $N$ $A_1$ $\vdots$ $A_N$

The first line consists of a single integer $N$ ($1 \le N \le 1000$). The $i+1$-st line consists of an integer $A_i$ ($1 \le A_i \le 10^9$ for $1 \le i \le N$).

Output

Print the maximum sum of all the numbers in the friendly sequence which can be obtained from the initial sequence.

Examples

Input| Output
---|---


6
1
2
3
4
5
6


|


12



3
173
1733
111733


|


111733



4
1
1
1
1


|


0



10
999999999
999999999
999999999
999999999
999999999
999999999
999999999
999999999
999999999
999999999


|


9999999990



1
999999999


|


999999999



10
28851
8842
9535
2311
25337
26467
12720
10561
8892
6435


|


56898






Example

Input




Output

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <queue>
#include <math.h>
#include <set>
#include <random>
#define FOR(i, n, m) for(ll i = n; i < (int)m; i++)
#define REP(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define pb push_back
using namespace std;
using ll = std::int_fast64_t;
using P = pair<ll, ll>;
constexpr ll inf = 1000000000;
constexpr ll mod = 1000000007;
constexpr long double eps = 1e-15;

template<typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2> p) {
    os << to_string(p.first) << " " << to_string(p.second);
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
    REP(i, v.size()) {
        if(i) os << " ";
        os << to_string(v[i]);
    }
    return os;
}

struct modint {
    ll n;
public:
    modint(const ll n = 0) : n((n % mod + mod) % mod) {}
    static modint pow(modint a, int m) {
        modint r = 1;
        while(m > 0) {
            if(m & 1) { r *= a; }
            a = (a * a); m /= 2;
        }
        return r;
    }
    modint &operator++() { *this += 1; return *this; }
    modint &operator--() { *this -= 1; return *this; }
    modint operator++(int) { modint ret = *this; *this += 1; return ret; }
    modint operator--(int) { modint ret = *this; *this -= 1; return ret; }
    modint operator~() const { return (this -> pow(n, mod - 2)); } // inverse
    friend bool operator==(const modint& lhs, const modint& rhs) {
        return lhs.n == rhs.n;
    }
    friend bool operator<(const modint& lhs, const modint& rhs) {
        return lhs.n < rhs.n;
    }
    friend bool operator>(const modint& lhs, const modint& rhs) {
        return lhs.n > rhs.n;
    }
    friend modint &operator+=(modint& lhs, const modint& rhs) {
        lhs.n += rhs.n;
        if (lhs.n >= mod) lhs.n -= mod;
        return lhs;
    }
    friend modint &operator-=(modint& lhs, const modint& rhs) {
        lhs.n -= rhs.n;
        if (lhs.n < 0) lhs.n += mod;
        return lhs;
    }
    friend modint &operator*=(modint& lhs, const modint& rhs) {
        lhs.n = (lhs.n * rhs.n) % mod;
        return lhs;
    }
    friend modint &operator/=(modint& lhs, const modint& rhs) {
        lhs.n = (lhs.n * (~rhs).n) % mod;
        return lhs;
    }
    friend modint operator+(const modint& lhs, const modint& rhs) {
        return modint(lhs.n + rhs.n);
    }
    friend modint operator-(const modint& lhs, const modint& rhs) {
        return modint(lhs.n - rhs.n);
    }
    friend modint operator*(const modint& lhs, const modint& rhs) {
        return modint(lhs.n * rhs.n);
    }
    friend modint operator/(const modint& lhs, const modint& rhs) {
        return modint(lhs.n * (~rhs).n);
    }
};
istream& operator>>(istream& is, modint m) { is >> m.n; return is; }
ostream& operator<<(ostream& os, modint m) { os << m.n; return os; }

#define MAX_N 3030303
long long extgcd(long long a, long long b, long long& x, long long& y) {
    long long d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1; y = 0;
    }
    return d;
}
long long mod_inverse(long long a, long long m) {
    long long x, y;
    if(extgcd(a, m, x, y) == 1) return (m + x % m) % m;
    else return -1;
}
vector<long long> fact(MAX_N+1, inf);
long long mod_fact(long long n, long long& e) {
    if(fact[0] == inf) {
        fact[0]=1;
        if(MAX_N != 0) fact[1]=1;
        for(ll i = 2; i <= MAX_N; ++i) {
            fact[i] = (fact[i-1] * i) % mod;
        }
    }
    e = 0;
    if(n == 0) return 1;
    long long res = mod_fact(n / mod, e);
    e += n / mod;
    if((n / mod) % 2 != 0) return (res * (mod - fact[n % mod])) % mod;
    return (res * fact[n % mod]) % mod;
}
// return nCk
long long mod_comb(long long n, long long k) {
    if(n < 0 || k < 0 || n < k) return 0;
    long long e1, e2, e3;
    long long a1 = mod_fact(n, e1), a2 = mod_fact(k, e2), a3 = mod_fact(n - k, e3);
    if(e1 > e2 + e3) return 0;
    return (a1 * mod_inverse((a2 * a3) % mod, mod)) % mod;
}

using mi = modint;

mi mod_pow(ll a, ll n) {
    mi ret = 1;
    mi tmp = a;
    while(n > 0) {
        if(n % 2) ret *= tmp;
        tmp = tmp * tmp;
        n /= 2;
    }
    return ret;
}

set<int> s;
vector<int> v;
int n;
vector<int> a(1010);

void pr(int a) {
    bool upd = true;
    while(a > 1 && upd) {
        upd = false;
        for(int i = 2; i * i <= a; i++) {
            if(a % i == 0) {
                v.pb(i);
                a /= i;
                upd = true;
                break;
            }
        }
    }
    if(a > 1) v.pb(a);
    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    REP(i, n) cin >> a[i];
    REP(i, n) pr(a[i]);
    REP(i, v.size()) s.insert(v[i]);
    ll ans = 0;
    for(auto elm: s) {
        ll sum = 0;
        REP(i, n) {
            if(a[i] % elm == 0) sum += a[i];
        }
        ans = max(ans, sum);
    }
    cout << ans << endl;
    return 0;
}