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>
 
using std::pair;
using std::vector;
using std::string;

typedef long long ll;
typedef pair<int, int> pii;
 
#define fst first
#define snd second
#define pb(a) push_back(a)
#define mp(a, b) std::make_pair(a, b)
#define debug(...) fprintf(stderr, __VA_ARGS__)
 
template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
 
const int oo = 0x3f3f3f3f;
 
template<typename T> T read(T& x) {
    int f = 1; x = 0;
    char ch = getchar();
    for(;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48; 
    return x *= f;
}

const int N = 500;
const int prime[] = { 2, 3, 5, 7, 11, 13, 17, 19 };
const int limit[] = { 8, 5, 3, 3, 2,  2,  2,  2  };

int n;
int num[N + 5], pri[N + 5][9];
int val[N + 5], tmp[N + 5], coe[9];

int work() {
    int res = 0;
    memset(tmp, 0, sizeof tmp);

    for(int i = 1; i <= num[0]; ++i) {
        int x = num[i];

        bool flag = true;
        for(int j = 0; j < 8; ++ j) {
            flag &= coe[j] >= pri[x][j];
        }

        if(flag) {
            if(pri[x][8] == 1) 
                res += val[x];
            else 
                tmp[pri[x][8]] += val[x];
        }
    }
    for(int i = 1; i <= N; ++i) res += std::max(tmp[i], 0);
    return res;
}

int ans = -oo;
void dfs(int cur) {
    if(cur == 8) {
        chkmax(ans, work());
        return;
    }

    for(coe[cur] = 0; coe[cur] <= limit[cur]; ++ coe[cur]) {
        dfs(cur + 1);
    }
}

int main() {

    read(n);
    for(int i = 1; i <= n; ++i) {
        static int m, v;
        read(m); read(v); val[m] += v; 
    }

    for(int i = 1; i <= N; ++i) if(val[i]) {
        num[++ num[0]] = i;

        int k = i;
        for(int j = 0; j < 8; ++j) {
            while(k % prime[j] == 0) {
                ++ pri[i][j];
                k /= prime[j];
            }
        }
        pri[i][8] = k;
    }

    dfs(0);
    printf("%d\n", ans);

    return 0;
}
