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;

using int64 = long long;
const int64 INF = 1LL << 59;

unordered_map< int64, int > prime_factor(int64 n)
{
  unordered_map< int64, int > ret;
  for(int64 i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return (ret);
}

int Q;
pair< unordered_map< int64, int >, int > vv[300];

int64 rec(vector< pair< int, int > > &conv, vector< int > &candidate, int idx, bool flag)
{
  int64 ret = 0;

  if(candidate.empty()) {
    return (ret);
  }

  if(flag) {
    for(auto &j : candidate) ret += vv[j].second;
  }

  if(idx < conv.size()) {

    if(conv[idx].first >= 17 && flag) {

      vector< int > used(Q, 0);
      int64 calc = 0;
      for(int i = idx; i < conv.size(); i++) {
        int64 beet = 0;
        if(conv[idx].first == 17) {
          int64 beet2 = 0;
          for(auto &j : candidate) {
            if(vv[j].first.count(conv[i].first)) {
              if(vv[j].first[conv[i].first] == 2) beet += vv[j].second;
              else beet2 += vv[j].second, beet += vv[j].second;
              used[j] = true;
            }
          }
          calc += max(0LL, max(beet, beet2));
          continue;
        }

        for(auto &j : candidate) {
          if(vv[j].first.count(conv[i].first)) {
            beet += vv[j].second;
            used[j] = true;
          }
        }
        calc += max(0LL, beet);
      }
      for(auto &j : candidate) {
        if(!used[j]) calc += vv[j].second;
      }
      ret = max(ret, calc);

    } else {
      set< vector< int > > used;
      for(int i = 0; i <= conv[idx].second + 1; i++) {
        vector< int > nt;
        for(int j : candidate) {
          if(vv[j].first.count(conv[idx].first)) {
            if(vv[j].first[conv[idx].first] > i) continue;
          }
          nt.emplace_back(j);
        }
        if(used.count(nt)) continue;
        used.emplace(nt);
        ret = max(ret, rec(conv, nt, idx + 1, flag | (i > 0)));
      }
    }
  }
  return (ret);
}


int main()
{
  cin >> Q;
  map< int, int > mx;
  for(int i = 0; i < Q; i++) {
    int m, x;
    cin >> m >> x;
    auto latte = prime_factor(m);
    for(auto &p : latte) {
      mx[p.first] = max(mx[p.first], p.second);
    }
    vv[i] = {latte, x};
  }
  vector< pair< int, int > > convert(begin(mx), end(mx));
  vector< int > candidate(Q);
  iota(begin(candidate), end(candidate), 0);
  cout << rec(convert, candidate, 0, false) << endl;
}