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 <fstream>
#include <cassert>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#include <complex>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<61;
const double pi=acos(-1);
const double eps=1e-7;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

map<int,int> Prime_Factor(int n){
	map<int,int> m;
	for(int i=2;i*i<=n;i++){
		while(n%i==0){
			m[i]++;
			n/=i;
		}
	}
	if(n!=1) m[n]++;
	return m;
}

const int N=7;

int n,S;
vi x,a;
map<int,int> m[300],pm;

int dfs(int I,vi& b){
	if(b.size()==N){
		vi c(S);
		int res=0;
		for(int i=0;i<n;i++){
			bool B=1;
			int ind=-1;
			for(auto j=m[i].begin();j!=m[i].end();j++){
				int key=j->first,num=j->second,J=pm[key];
				if(J<N){
					if(b[J]<num) B=0;
				}
				else ind=J;
			}
			if(B){
				if(ind==-1) res+=x[i];
				else c[ind]+=x[i];
			}
		}
		for(int i=N;i<S;i++) if(c[i]>0) res+=c[i];
		return res;
	}
	int res=-inf,t=1,num=0;
	do{
		b.push_back(num);
		res=max(res,dfs(I+1,b));
		b.pop_back();
		t*=a[I];
		num++;
	}while(t<=300);
	return res;
}

int main(){
	cin>>n;
	x=vi(n);
	for(int i=0;i<n;i++){
		int M;
		cin>>M>>x[i];
		m[i]=Prime_Factor(M);
	}
	for(int i=2;i<=300;i++){
		bool B=1;
		for(int j=2;j*j<=i;j++) if(i%j==0) B=0;
		if(B){
			pm[i]=a.size();
			a.push_back(i);
		}
	}
	S=a.size();
	vi t;
	cout<<dfs(0,t)<<endl;
}