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 "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-12;

//int N, M, K, T, H, W, L, R;
long long int N, M, K, T, H, W, L, R;

vector<int> Prime(int num) {
	vector<int>ret;
	ret.push_back(2);
	ret.push_back(3);
	for (int i = 5; i <= num; i += 6) {
		bool flag = true;
		for (int j = 2; j < ret.size(); j++) {
			if (ret[j] * ret[j] > i)break;
			if (i%ret[j] == 0) {
				flag = false;
				break;
			}
		}
		if (flag)ret.push_back(i);
		flag = true;
		for (int j = 2; j < ret.size(); j++) {
			if (ret[j] * ret[j] > i + 2)break;
			if ((i + 2) % ret[j] == 0) {
				flag = false;
				break;
			}
		}
		if (flag)ret.push_back(i + 2);
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;
	vector<int>v(301);
	for (int i = 1; i <= N; i++) {
		cin >> L >> R;
		v[L] += R;
	}
	auto p = Prime(300);
	vector<int>div(301);
	for (int i = 1; i <= 300; i++) {
		div[i] = i;
		for (auto j : p) {
			if (j < 19)continue;
			if (i%j == 0)div[i] /= j;
		}
	}
	long long int ans = 0;
	for (long long int i = 1; i <= 300; i *= 2) {
		for (long long int j = 1; j <= 300; j *= 3) {
			for (long long int k = 1; k <= 300; k *= 5) {
				for (long long int l = 1; l <= 300; l *= 7) {
					for (long long int m = 1; m <= 300; m *= 11) {
						for (long long int n = 1; n <= 300; n *= 13) {
							for (long long int o = 1; o <= 300; o *= 17) {
								long long int box = i * j*k*l*m*n*o;
								long long int c = 0;
								for (int num = 2; num <= 300; num++) {
									if (box%num==0)c += v[num];
								}
								for (auto num : p) {
									if (num < 19)continue;
									int add = 0;
									for (int a = num; a <= 300; a += num) {
										if(box%(a/num)==0)add += v[a];
									}
									c += max(add, 0);
								}
								ans = max(ans, c);
							}
						}
					}
				}
			}
		}
	}
	cout << ans << endl;
}