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 long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int q,m[305],x[305];
int p[7]={2,3,5,7,11,13,17};
int main(){
	cin>>q;
	for(int i=0;i<q;i++) cin>>m[i]>>x[i];
	int ret = -INF;
	for(int x2=1;x2<=300;x2*=2)	for(int x3=1;x3<=300;x3*=3)	for(int x5=1;x5<=300;x5*=5)	for(int x7=1;x7<=300;x7*=7)	for(int x11=1;x11<=300;x11*=11)	for(int x13=1;x13<=300;x13*=13)	for(int x17=1;x17<=300;x17*=17){
		int ans = 0;
		map<int,int>MM;
		for(int i=0;i<q;i++){
			int M = m[i];
			int m2 = 1,m3 = 1,m5 = 1,m7 = 1,m11 = 1,m13 = 1,m17 = 1;
			while(M%2 == 0){ M/=2; m2*=2; }
			while(M%3 == 0){ M/=3; m3*=3; }
			while(M%5 == 0){ M/=5; m5*=5; }
			while(M%7 == 0){ M/=7; m7*=7; }
			while(M%11 == 0){ M/=11; m11*=11; }
			while(M%13 == 0){ M/=13; m13*=13; }
			while(M%17 == 0){ M/=17; m17*=17; }
			
			if(x2<m2 || x3<m3 || x5<m5 || x7<m7 || x11<m11 || x13<m13 || x17<m17) continue;
			if(M == 1) ans += x[i];
			else MM[M] += x[i];
		}
		for(map<int,int>::iterator it=MM.begin();it!=MM.end();++it) ans += max(0,it->sc);
		ret = max(ret,ans);
	}
	cout << ret << endl;
}