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 <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const int MAX=301;
vector<int> prime;
bool isprime[MAX];
void sieve(){
	for(int i=3; i<MAX; i+=2){
		isprime[i]=1;
	}
	isprime[2]=1;
	prime.push_back(2);
	for(int i=3; i<MAX; i++){
		if(isprime[i]){
			prime.push_back(i);
			for(int j=2*i; j<MAX; j+=i){
				isprime[j]=0;
			}
		}
	}
	return;
}
int x[303];
int main()
{
	int q;
	cin>>q;
	for(int i=0; i<q; i++){
		int m, xi; cin>>m>>xi;
		x[m]=xi;
	}
	vector<vector<int>> vx[303];
	sieve();
	for(int i=2; i<=300; i++){
		vector<int> v(prime.size());
		int x=i;
		int k=0;
		for(int j=0; j<prime.size(); j++){
			while(x%prime[j]==0){
				x/=prime[j];
				v[j]++;
				k=max(k, j);
			}
		}
		v.push_back(i);
		vx[k].push_back(v);
	}
	map<vector<int>, int> mp;
	vector<int> v0(1);
	int s0=0;
	for(int i=0; i<9; i++){
		s0+=x[1<<i];
		mp[v0]=s0;
		v0[0]++;
	}
	for(int i=0; i<prime.size()-1; i++){
		int q=prime[i+1];
		map<vector<int>, int> tmp;
		for(auto p:mp){
			vector<int> v=p.first;
			for(int j=0; j<=i; j++){
				int x1=1;
				for(int k=0; k<v[j]; k++){
					x1*=prime[j];
					if(x1>300/q){
						v[j]=k;
						break;
					}
				}
			}
			int x1=1;
			v.push_back(0);
			for(int j=0; j<10; j++){
				int s=0;
				for(auto w:vx[i+1]){
					bool dame=0;
					for(int k=0; k<=i+1; k++){
						if(w[k]>v[k]){
							dame=1;
							break;
						}
					}
					if(!dame){
						s+=x[w.back()];
					}
				}
				if(tmp.find(v)==tmp.end()) tmp[v]=p.second+s;
				else tmp[v]=max(tmp[v], p.second+s);
				v.back()++;
				x1*=q;
				if(x1>300) break;
			}
		}
		swap(mp, tmp);
		//cout<<prime[i]<<" "<<mp.size()<<endl;
	}
	int ans=0;
	for(auto p:mp){
		ans=max(ans, p.second);
	}
	cout<<ans<<endl;
	return 0;
}