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 sz(x) (int)x.size() 
#define pb push_back 
#define mp make_pair 
#define fi(a, b) for(int i=a; i<=b; i++) 
#define fj(a, b) for(int j=a; j<=b; j++) 
#define fo(a, b) for(int o=a; o<=b; o++) 
#define fdi(a, b) for(int i=a; i>=b; i--) 
#define fdj(a, b) for(int j=a; j>=b; j--) 
#define fdo(a, b) for(int o=a; o>=b; o--) 

#ifdef LOCAL
#define err(...) fprintf(stderr, __VA_ARGS__)
#else
#define err(...) while(false) {}
#endif

typedef long long ll; 
typedef pair<int, int> pii; 
typedef pair<ll, ll> pll; 
typedef vector<int> vi; 
typedef vector<ll> vll;
typedef vector<pii> vpii; 
typedef vector<pll> vpll; 
typedef long double ld;
typedef unsigned long long ull;

/////////////////////////////////

int const MAX = 341;

int q;
int m[MAX];
int x[MAX];

ll ans;

int l[MAX];
vi primes;

void sieve() {
	fi(2, MAX - 1) {
		if (!l[i]) {
			for (int j = i; j < MAX; j += i) {
				if (l[j] == 0 || l[j] > i) l[j] = i;
			}
			primes.pb(i);
		}
	}
}

int cnt[MAX];

int const K = 19;

bool can(int x) {
	while (x > 1) {
		int k = l[x];
		int d = 0;
		while (x % k == 0) {
			x /= k;
			d++;
		}
		if (cnt[k] < d) return 0;
	}
	return 1;
}

void calc() {
	vll a(MAX, 0LL);

	fi(1, q) {
		int x = m[i];
		bool ok = true;
		while (x > 1) {
			int k = l[x];
			if (k >= K) break;
			int d = 0;
			while (x % k == 0) {
				x /= k;
				d++;
			}
			if (cnt[k] < d) ok = false;
		}
		if (ok && x != 1) {
			a[x] += ::x[i];
		}
	}

	for (int x : primes) {
		if (x < K) continue;
		if (a[x] > 0) {
			cnt[x] = 1;
		} else {
			cnt[x] = 0;
		}
	}
	
	ll cur = 0;
	fi(1, q) {
		if (can(m[i])) {
			cur += x[i];
		}
	}

	ans = max(ans, cur);
}

void go(int x) {
	if (primes[x] >= K) {
		calc();
		return;
	}
	int cur = 1;
	fo(0, 100) {
		if (cur >= MAX) break;
		cnt[primes[x]] = o;
		go(x + 1);
		cur *= primes[x];
	}
}

void solve() {
	sieve();
	go(0);	
	printf("%lld\n", ans);
}

int main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

  scanf("%d", &q);
  fi(1, q) {
  	scanf("%d %d", &m[i], &x[i]);
  }
	solve();		

	
#ifdef LOCAL
	err("ELAPSED TIME: %.3Lf\n", (ld) clock() / CLOCKS_PER_SEC);
#endif	
	
	return 0;
}