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 namespace std;
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) GET_MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 1000000009

vector<int> primes = {2,3,5,7,11,13,17};
int nprime = primes.size();
vector<pair<int,int>> v;

int dfs(int d, map<int,int> state){
  if(d == nprime){
    // solve
    int ret = 0;
    map<int,int> tmp;
    for(auto p : v){
      bool ok = true;
      for(auto &sp : state){
        int c = 0;
        while(p.first%sp.first == 0){
          p.first /= sp.first;
          c++;
        }
        if(c > sp.second){
          ok = false;
          break;
        }
      }
      if(ok){
        if(p.first == 1) ret += p.second;
        else tmp[p.first] += p.second;
      }
    }
    for(auto &p : tmp) if(p.second>0) ret += p.second;
    // dbg(ret, vector<pair<int,int>>(all(state)));
    return ret;
  }
  else {
    int ret = -INF;
    state[primes[d]] = -1;
    for(int x=1; x<=300; x *= primes[d]){
      state[primes[d]]++;
      ret = max(ret, dfs(d+1, state));
    }
    return ret;
  }
}

int main(){
  int q;
  cin>>q;
  v.resize(q);
  rep(i,q){
    cin>>v[i].first>>v[i].second;
  }

  cout << dfs(0, map<int,int>()) << endl;

  return 0;
}
