Consider an infinite sequence a_1, a_2, … Initially, the values of all the terms are 0, and from this state we will sequentially perform Q operations. The i-th operation (1 ≤ i ≤ Q) is as follows:

* For every positive integer j, add x_i to the value of a_{j × m_i}.



Find the value of the largest term after these Q operations.

Constraints

* 1 ≤ Q ≤ 299
* 2 ≤ m_i ≤ 300
* -10^6 ≤ x_i ≤ 10^6
* All m_i are distinct.
* All input values are integers.

Input

Input is given from Standard Input in the following format:


Q
m_1 x_1
:
m_Q x_Q


Output

Print the value of the largest term after the Q operations.

Examples

Input

3
2 10
3 -20
6 15


Output

10


Input

3
10 -3
50 4
100 -5


Output

1


Input

5
56 114834
72 -149861
100 190757
192 -132693
240 133108


Output

438699
#include <bits/stdc++.h>

#define VARNAME(x) #x
#define show(x) cerr << #x << " = " << x << endl

using namespace std;
using ll = long long;

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
    os << "sz:" << v.size() << "\n[";
    for (const auto& p : v) {
        os << p << ",";
    }
    os << "]\n";
    return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v)
{
    for (auto& e : v) {
        is >> e;
    }
    return is;
}

template <typename S, typename T>
ostream& operator<<(ostream& os, const pair<S, T>& p)
{
    os << "(" << p.first << "," << p.second
       << ")";
    return os;
}


constexpr ll MOD = (ll)1e9 + 7LL;

template <typename T>
constexpr T INF = numeric_limits<T>::max() / 10;

using V7 = vector<vector<vector<vector<vector<vector<vector<ll>>>>>>>;
using V6 = vector<vector<vector<vector<vector<vector<ll>>>>>>;
using V5 = vector<vector<vector<vector<vector<ll>>>>>;
using V4 = vector<vector<vector<vector<ll>>>>;
using V3 = vector<vector<vector<ll>>>;
using V2 = vector<vector<ll>>;
using V1 = vector<ll>;


struct Data {
    vector<int> ind;
    ll x;
};

constexpr int MAX = 300;
constexpr int SQRT = 18;
constexpr int LP = 7;
constexpr int prime[LP] = {2, 3, 5, 7, 11, 13, 17};
const vector<int> maxind{9, 6, 4, 3, 3, 3, 3};
int pnum = 0;

bool div(const vector<int>& index, const vector<int>& ind)
{
    for (int i = 0; i < index.size(); i++) {
        if (index[i] < ind[i]) {
            return false;
        }
    }
    return true;
}

void For(const int d, const vector<int>& sup, vector<int>& index, vector<V7>& value, const vector<vector<Data>>& data, ll& maximum)
{
    if (d == index.size()) {
        ll sum = 0;
        for (int i = 0; i <= pnum; i++) {
            for (const auto& d : data[i]) {

                if (div(index, d.ind)) {
                    value[i][index[0]][index[1]][index[2]][index[3]][index[4]][index[5]][index[6]] += d.x;
                }
            }
            if (i == 0) {
                sum += value[i][index[0]][index[1]][index[2]][index[3]][index[4]][index[5]][index[6]];
            } else {
                sum += max(0LL, value[i][index[0]][index[1]][index[2]][index[3]][index[4]][index[5]][index[6]]);
            }
        }
        maximum = max(maximum, sum);
    } else {
        for (int i = 0; i < sup[d]; i++) {
            index[d] = i;
            For(d + 1, sup, index, value, data, maximum);
        }
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    auto isprime = [](const int n) {
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    };
    map<int, int> mp;
    mp[1] = 0;
    for (int i = SQRT; i <= MAX; i++) {
        if (isprime(i)) {
            pnum++;
            mp[i] = pnum;
        }
    }

    vector<V7> value(pnum + 1, V7(maxind[0], V6(maxind[1], V5(maxind[2], V4(maxind[3], V3(maxind[4], V2(maxind[5], V1(maxind[6], 0))))))));

    int Q;
    cin >> Q;
    vector<vector<Data>> data(pnum + 1);
    for (int i = 0; i < Q; i++) {
        ll m, x;
        cin >> m >> x;
        vector<int> num(LP, 0);
        for (int j = 0; j < LP; j++) {
            while (m % prime[j] == 0) {
                num[j]++;
                m /= prime[j];
            }
        }
        data[mp[m]].push_back(Data{num, x});
    }

    vector<int> index(LP, 0);
    ll maximum = 0;
    For(0, maxind, index, value, data, maximum);
    cout << maximum << endl;


    return 0;
}
