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;

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cout << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

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

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

bool pr[310];
vector<pii> vec;
vi big;
int ans;
int q;
int m[310], x[310];
vi sum;
vi deg;
vi xdeg[310];

void check() {
	vi sum(big.size());
	int t = 0;

	rep(i, q) {
		bool ok = true;
		rep(j, vec.size()) {
			if (deg[j] < xdeg[i][j]) {
				ok = false;
			}
		}
		if (ok) {
			bool f = 1;
			rep(j, big.size()) {
				if (m[i] % big[j] == 0) {
					sum[j] += x[i];
					f = 0;
				}
			}
			if (f) {
				t += x[i];
			}
		}
	}
	rep(i, sum.size()) {
		t += max(0, sum[i]);
	}
	ans = max(ans, t);
}

void dfs(int p) {
	if (p == vec.size()) {
		check();
		return ;
	}

	for (int i = 0; i <= vec[p].se; ++i) {
		deg[p] = i;
		dfs(p + 1);
	}
}

int main() {
	for (int i = 2; i <= 300; ++i) {
		if (!pr[i]) {
			for (int j = i * 2; j <= 300; j += i) {
				pr[j] = 1;
			}
			if (i * i <= 300) {
				int c = 1, x = i;
				while (x * i <= 300) {
					x *= i;
					++c;
				}
				vec.eb(i, c);
			} else {
				big.pb(i);
			}
		}
	}

	cin >> q;
	rep(i, q) {
		cin >> m[i] >> x[i];
	}

	sum.resize(big.size());
	deg.resize(vec.size());

	rep(i, q) {
		xdeg[i].resize(vec.size());
		int c = 0;
		rep(j, vec.size()) {
			int v = m[i];
			int c = 0;
			while (v % vec[j].fi == 0) {
				c++;
				v /= vec[j].fi;
			}
			xdeg[i][j] = c;
		}
	}

	dfs(0);
	cout << ans << endl;

	return 0;
}