求救！！！！！！！！！！！！！！

扭动的树

Description

有一棵以key为键值以val为权值的二叉查找树（左子树的key值都比根节点key值小，右子树的key值都比根节点的key值大），定义其某个节点的sum为它的子树内节点的val值之和。给出n个<key, val>正整数对，现需保证这棵树上任意一条边的两个端点的key值的最大公约数不为1，询问这棵树上所有节点的sum之和最大可能是多少。如果这棵树不存在任意一个合法形态，输出-1。

Input

第一行为一个整数n。
接下来n行每行两个正整数key[i], val[i]。

Output

输出仅一行一个整数表示答案。

Sample Input

6
8 1
8 1
9 4
4 5
6 1
4 4

Sample Output

45

Hint

对于1号测试点（5%）：key[i]=1。
对于1~3号测试点（15%）：1≤n≤10。
对于1~10号测试点（50%）：1≤n≤50。
对于4~14号测试点（55%）：key[i]互不相同。
对于15~16号测试点（10%）：所有key[i]都相同。
对于所有测试点（100%）：1≤n≤300,1≤key[i]≤10^18,1≤val[i]≤10^6。

Source

2018NOIP国庆集训