有 n位同学排成一列进行传球游戏。可以用 ai 来表示第 i位同学的性格值，用 bi 来描述其渴望度。 对于一轮游戏，一开始球可以在任意一位同学手上，拿到球的同学可以把球传给后面的任意一位朋友（两位同学是朋友当且仅当他们的性格值不互质）。 现在请你回答一局游戏中所有拿到过球的同学的渴望度之和最大为多少。

共 n+1行。 第一行一个正整数 n，表示同学的数量。 
第 i+1 行两个正整数 ai, bi，分别表示第 i位同学的性格值和渴望度。 (1≤i≤n)

一行一个正整数表示一局游戏中所有拿到过球的同学的渴望度之和的最大值。

【样例说明】 样例解释：一开始在第 2 位手上，第 2 位传给第 3 位，第 3 位传给第 5 位。


【数据范围】
30%的数据，1≤n ≤ 50； 
70%的数据， 1≤ n≤ 1000
100%的数据， 1≤ n≤ 10^5
对于所有的数据，1≤ai≤10^6， 1≤bi≤10^9。