p03512 Code Festival Team Relay (Parallel) - Akashic Records_28754
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

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Main {
	static InputStream is;
	static PrintWriter out;
	static String INPUT = "";
	
	static void solve()
	{
		int Q = ni();
		int[][] qs = new int[Q][];
		for(int z = 0;z < Q;z++){
			qs[z] = new int[]{ni(), ni()};
		}
		
		int[] primes = sieveEratosthenes(300);
		int[][][][][][][] dp = new int[9][6][4][3][3][3][3];
		int[][] mfs = new int[305][7];
		int[] rem = new int[305];
		for(int i = 1;i <= 300;i++){
			int j = i;
			for(int k = 0;k < 7;k++){
				while(j % primes[k] == 0){
					j /= primes[k];
					mfs[i][k]++;
				}
			}
			rem[i] = j;
		}
		
		for(int[] q : qs){
			if(rem[q[0]] == 1){
				for(int i = mfs[q[0]][0];i < 9;i++){
					for(int j = mfs[q[0]][1];j < 6;j++){
						for(int k = mfs[q[0]][2];k < 4;k++){
							for(int l = mfs[q[0]][3];l < 3;l++){
								for(int m = mfs[q[0]][4];m < 3;m++){
									for(int n = mfs[q[0]][5];n < 3;n++){
										for(int o = mfs[q[0]][6];o < 3;o++){
											dp[i][j][k][l][m][n][o] += q[1];
										}
									}
								}
							}
						}
					}
				}
			}
		}
		
		for(int p : primes){
			if(p >= 19){
				int[][][][][][][] plus = new int[9][6][4][3][3][3][3];
				for(int[] q : qs){
					if(rem[q[0]] == p){
						int r = q[0] / rem[q[0]];
						int x = q[1];
//						plus[mfs[r][0]][mfs[r][1]][mfs[r][2]][mfs[r][3]][mfs[r][4]][mfs[r][5]][mfs[r][6]] += x;
						for(int i = mfs[r][0];i < 9;i++){
							for(int j = mfs[r][1];j < 6;j++){
								for(int k = mfs[r][2];k < 4;k++){
									for(int l = mfs[r][3];l < 3;l++){
										for(int m = mfs[r][4];m < 3;m++){
											for(int n = mfs[r][5];n < 3;n++){
												for(int o = mfs[r][6];o < 3;o++){
													plus[i][j][k][l][m][n][o] += q[1];
												}
											}
										}
									}
								}
							}
						}
					}
				}
				for(int i = 8;i >= 0;i--){
					for(int j = 5;j >= 0;j--){
						for(int k = 3;k >= 0;k--){
							for(int l = 2;l >= 0;l--){
								for(int m = 2;m >= 0;m--){
									for(int n = 2;n >= 0;n--){
										for(int o = 2;o >= 0;o--){
//											int my = 0;//plus[i][j][k][l][m][n][o];
//											if(i+1 < 9){
//												my = Math.max(my, plus[i+1][j][k][l][m][n][o]);
//											}
//											if(j+1 < 6){
//												my = Math.max(my, plus[i][j+1][k][l][m][n][o]);
//											}
//											if(k+1 < 4){
//												my = Math.max(my, plus[i][j][k+1][l][m][n][o]);
//											}
//											if(l+1 < 3){
//												my = Math.max(my, plus[i][j][k][l+1][m][n][o]);
//											}
//											if(m+1 < 3){
//												my = Math.max(my, plus[i][j][k][l][m+1][n][o]);
//											}
//											if(n+1 < 3){
//												my = Math.max(my, plus[i][j][k][l][m][n+1][o]);
//											}
//											if(o+1 < 3){
//												my = Math.max(my, plus[i][j][k][l][m][n][o+1]);
//											}
//											my += plus[i][j][k][l][m][n][o];
//											plus[i][j][k][l][m][n][o] = my;
											dp[i][j][k][l][m][n][o] += Math.max(0, plus[i][j][k][l][m][n][o]);
										}
									}
								}
							}
						}
					}
				}
			}
		}
		
		int ans = Integer.MIN_VALUE;
		for(int i = 8;i >= 0;i--){
			for(int j = 5;j >= 0;j--){
				for(int k = 3;k >= 0;k--){
					for(int l = 2;l >= 0;l--){
						for(int m = 2;m >= 0;m--){
							for(int n = 2;n >= 0;n--){
								for(int o = 2;o >= 0;o--){
									ans = Math.max(ans, dp[i][j][k][l][m][n][o]);
								}
							}
						}
					}
				}
			}
		}
		
		out.println(ans);
//		
//		tr(primes.length);
	}
	
	
	public static int[][] factorFast(int n, int[] lpf)
	{
		int[][] f = new int[9][];
		int q = 0;
		while(lpf[n] > 0){
			int p = lpf[n];
			if(q == 0 || p != f[q-1][0]){
				f[q++] = new int[]{p, 1};
			}else{
				f[q-1][1]++;
			}
			n /= p;
		}
		if(n > 1){
			// big prime
			return new int[][]{{n, 1}};
		}
		return Arrays.copyOf(f, q);
	}

	
	public static int[] enumLowestPrimeFactors(int n)
	{
		int tot = 0;
		int[] lpf = new int[n+1];
		int u = n+32;
		double lu = Math.log(u);
		int[] primes = new int[(int)(u/lu+u/lu/lu*1.5)];
		for(int i = 2;i <= n;i++)lpf[i] = i;
		for(int p = 2;p <= n;p++){
			if(lpf[p] == p)primes[tot++] = p;
			int tmp;
			for(int i = 0;i < tot && primes[i] <= lpf[p] && (tmp = primes[i]*p) <= n;i++){
				lpf[tmp] = primes[i];
			}
		}
		return lpf;
	}

	
	public static int[] sieveEratosthenes(int n) {
		if (n <= 32) {
			int[] primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };
			for (int i = 0; i < primes.length; i++) {
				if (n < primes[i]) {
					return Arrays.copyOf(primes, i);
				}
			}
			return primes;
		}

		int u = n + 32;
		double lu = Math.log(u);
		int[] ret = new int[(int) (u / lu + u / lu / lu * 1.5)];
		ret[0] = 2;
		int pos = 1;

		int[] isnp = new int[(n + 1) / 32 / 2 + 1];
		int sup = (n + 1) / 32 / 2 + 1;

		int[] tprimes = { 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };
		for (int tp : tprimes) {
			ret[pos++] = tp;
			int[] ptn = new int[tp];
			for (int i = (tp - 3) / 2; i < tp << 5; i += tp)
				ptn[i >> 5] |= 1 << (i & 31);
			for (int j = 0; j < sup; j += tp) {
				for (int i = 0; i < tp && i + j < sup; i++) {
					isnp[j + i] |= ptn[i];
				}
			}
		}

		// 3,5,7
		// 2x+3=n
		int[] magic = { 0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13, 31, 22, 28, 18, 26, 10, 7, 12, 21, 17,
				9, 6, 16, 5, 15, 14 };
		int h = n / 2;
		for (int i = 0; i < sup; i++) {
			for (int j = ~isnp[i]; j != 0; j &= j - 1) {
				int pp = i << 5 | magic[(j & -j) * 0x076be629 >>> 27];
				int p = 2 * pp + 3;
				if (p > n)
					break;
				ret[pos++] = p;
				if ((long) p * p > n)
					continue;
				for (int q = (p * p - 3) / 2; q <= h; q += p)
					isnp[q >> 5] |= 1 << q;
			}
		}

		return Arrays.copyOf(ret, pos);
	}

	
	public static void main(String[] args) throws Exception
	{
		long S = System.currentTimeMillis();
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		solve();
		out.flush();
		long G = System.currentTimeMillis();
		tr(G-S+"ms");
	}
	
	private static boolean eof()
	{
		if(lenbuf == -1)return true;
		int lptr = ptrbuf;
		while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
		
		try {
			is.mark(1000);
			while(true){
				int b = is.read();
				if(b == -1){
					is.reset();
					return true;
				}else if(!isSpaceChar(b)){
					is.reset();
					return false;
				}
			}
		} catch (IOException e) {
			return true;
		}
	}
	
	private static byte[] inbuf = new byte[1024];
	static int lenbuf = 0, ptrbuf = 0;
	
	private static int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
//	private static boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); }
	private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private static double nd() { return Double.parseDouble(ns()); }
	private static char nc() { return (char)skip(); }
	
	private static String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private static char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private static char[][] nm(int n, int m)
	{
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private static int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private static int ni()
	{
		int num = 0, b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}

3
10 -3
50 4
100 -5 3
2 10
3 -20
6 15 5
56 114834
72 -149861
100 190757
192 -132693
240 133108 3
10 -3
50 4
101 -5 3
2 18
3 -20
6 15 5
56 114834
72 -134386
100 190757
192 -132693
240 133108 3
10 -3
91 4
101 -5 3
18 -3
91 4
101 1 5
92 114834
125 -176641
100 13125
192 -68478
240 133108 5
42 114834
125 -176641
100 13125
140 -68478
240 133108 3
44 -3
15 1
111 1 3
7 -3
15 0
110 0 3
2 18
4 -20
6 15 5
56 114834
72 -134386
100 190757
192 -132693
240 261716 5
56 114834
72 -134386
100 119537
192 -68478
240 133108 3
10 -3
91 7
101 0 5
56 114834
72 -176641
100 242597
192 -68478
240 133108 5
92 114834
125 -176641
100 13125
192 -68478
240 62192 3
36 -3
6 4
111 2 5
42 114834
125 -176641
100 13125
140 -39699
240 133108 3
44 -3
15 2
111 1 3
4 18
3 -20
2 18 3
44 -3
4 8
111 1 3
4 24
3 -20
2 18 5
25 114834
8 -149861
100 190757
104 -132693
240 133108 5
56 150056
72 -134386
100 190757
176 -65223
240 261716 3
4 47
3 -20
2 18 5
56 114834
78 -176641
101 372457
192 -68478
16 133108 5
92 114834
125 -176641
101 3465
192 -68478
189 62192 5
92 114834
125 -80332
110 13125
270 -102981
240 99516 5
92 217221
125 -17608
100 13125
31 -68478
240 133108 3
4 89
3 -20
2 18 5
92 384326
125 -17608
100 13125
31 -68478
240 133108 5
56 150056
72 -134386
100 190757
274 -65223
240 233516 3
4 9
3 -20
2 18 3
5 0
91 14
111 0 3
51 -4
176 4
111 4 5
56 150056
72 -134386
100 71353
274 -65223
240 233516 3
5 1
91 14
111 0 5
92 164718
125 -17608
100 13125
31 -5858
240 133108 5
33 114834
8 -110171
100 190757
104 -82350
240 133108 5
20 114834
37 -176641
101 557168
192 -68478
10 133108 5
92 114834
125 -71017
101 125951
124 -9260
46 133108 5
92 57423
125 -17608
100 13125
31 -5858
240 133108 5
33 114834
8 -110171
100 61496
104 -82350
240 133108 5
56 150056
72 -134034
100 50425
274 -65223
240 233516 5
107 114834
142 -28092
100 242597
171 -68478
41 180385 5
56 137351
72 -134034
100 50425
274 -65223
240 233516 5
51 114834
8 -110171
100 27913
104 -82350
240 133108 5
13 114834
72 -134386
110 119537
473 -25250
278 253378 5
107 114834
142 -28092
100 86682
122 -68478
41 180385 5
51 114834
7 -110171
100 27913
104 -82350
240 133108 5
56 137351
72 -52672
100 50425
274 -65223
240 130574 5
107 158676
240 -28092
100 86682
207 -68478
41 180385 5
75 114834
14 -110171
100 50568
104 -82350
240 133108 3
29 -6
4 11
110 0 5
282 57423
125 -17608
110 13125
66 -636
240 133108 5
75 114834
14 -110171
100 50568
50 -67233
240 133108 5
88 158676
240 -28092
100 86682
207 -82155
21 1454 5
282 57423
125 -17608
110 22314
66 -636
240 133108 5
282 57423
125 -17608
100 22314
66 -636
240 133108 5
75 114834
14 -110171
110 50568
50 -11199
240 133108 5
88 195113
240 -43027
100 86682
207 -82155
21 1454 5
282 44220
125 -17608
100 22314
66 -636
240 133108 5
282 7930
125 -17608
100 22314
66 -636
240 133108 5
148 138365
14 -110171
110 50568
50 -11199
240 133108 5
282 7930
62 -17608
100 15638
66 -636
240 133108 5
148 15741
14 -63165
110 50568
50 -11199
240 133108 5
88 195113
287 -43027
100 154868
276 -82155
24 1454 5
148 13198
14 -63165
110 50568
51 -11199
240 133108 5
88 195113
287 -26746
100 267245
276 -82155
24 1454 5
282 7930
104 -17608
100 29775
125 -413
240 133108 5
99 195113
287 -26746
100 267245
276 -82155
24 1065 5
282 7930
104 -17608
100 22712
125 -308
240 133108 5
282 7733
104 -17608
100 22712
125 -308
240 133108 5
148 13198
33 -16307
110 50568
157 -11199
240 133108 5
147 195113
287 -1106
100 267245
276 -82155
24 667 5
148 13198
33 -16307
110 76434
157 -11199
240 133108 5
148 13198
33 -16307
110 76434
157 -11199
240 60136 5
148 13198
33 -16307
110 22750
157 -11199
240 60136 5
148 23263
33 -16307
110 22750
157 -11199
240 60136 5
148 18310
33 -16307
110 22750
157 -11199
240 60136 5
228 195113
558 -71
100 267245
276 -18356
24 663 5
148 18310
33 -6616
110 22750
157 -11199
240 60136 5
148 18310
33 -2192
110 22750
157 -11199
240 60136 5
228 195113
225 -71
100 267245
276 -10163
11 802 5
228 195113
225 -71
100 267245
276 -10163
11 911 5
261 195113
225 -71
100 267245
276 -10163
2 911 5
261 195113
225 -71
100 169878
276 -10163
2 911 5
261 195113
225 -103
100 169878
276 -18616
2 911 5
261 195113
225 -103
101 169878
411 -30216
3 911 3
7 9
62 0
111 1 3
2 10
3 -4
6 15 5
56 114834
72 -149861
100 190757
25 -132693
240 133108 5
56 114834
72 -134386
100 42660
192 -132693
240 133108 5
56 64042
72 -134386
100 190757
192 -68478
240 133108 5
56 114834
72 -176641
100 190757
192 -68478
240 195018 5
92 114834
125 -176641
100 7291
140 -68478
240 133108 5
25 114834
2 -149861
100 190757
192 -132693
240 133108 3
2 1
4 -20
6 15 5
56 171149
72 -176641
100 242597
192 -68478
240 133108 5
92 114834
125 -176641
100 93986
192 -68478
46 133108 5
42 96508
125 -176641
100 13125
140 -39699
240 133108
1 10 438699 1
 18
 438699
 4
 5
 261067
 192589
 2
 0
 33
 567307
 367479
 7
 490539
 190151
 6
 221368
 3
 36
 9
 42
 305591
 602529
 65
 620399
 180491
 227475
 363454
 107
 530559
 574329
 27
 14
 8
 454925
 15
 310951
 328528
 805110
 373893
 203656
 199267
 433997
 537816
 421292
 165684
 487749
 381901
 275855
 318350
 425743
 298510
 11
 203020
 231277
 246812
 212209
 212845
 287311
 283249
 199642
 163352
 322041
 156676
 199417
 351435
 196874
 463812
 170813
 463423
 163750
 163553
 180567
 463025
 206433
 133461
 79777
 89842
 84889
 463021
 94580
 99004
 463160
 463269
 463198
 365831
 365799
 365902
 10
 21
 306006
 290602
 387907
 500609
 255233
 288838
 16
 546854
 341928
 203042
