O. 捕鱼达人！
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

小H是一位捕鱼达人，他经常驾驶船只出海捕鱼。

海上不仅有鱼，还有令人作呕的海洋垃圾。我们可以将海洋视为一个二维平面，小H的船在位置 (0, 0) 上。海上有 n 个物品，每个物品都有一个坐标和一个价值。第 i 个物品的价值可记作整数 vi，如果它是鱼，则 vi ≥ 0；如果是海洋垃圾，则 vi < 0。

小H有一张神奇的网。这个网可以视为 边界 过小船位置的一个圆。小H可以任意调整网的大小，甚至可以将其无限扩大，退化成一个半平面。现在，小H想知道他一次抛网所能获得的所有物品（包含圆边界上的物品）权值和最大是多少？

Input

第一行一个数 整数 n(0 < n ≤ 1000) 表示物品的总个数。

第二行 n 个整数，第 i 个整数 vi( - 107 ≤ vi ≤ 107) 表示第 i 个物品的权值。

接下来 n 行，每行两个整数 x, y( - 104 ≤ x, y ≤ 104) 表示第 i 个物品的坐标（保证物品坐标两两不同且不为原点）。

Output

输出一行一个整数，表示最大权值和。

Examples
Input
5
-1 -3 3 5 -2
-2 2
3 -1
-3 2
-1 4
5 -3
Output
7
Input
3
10 -8 -8
0 10
5 5
-5 5
Output
2
Note

第一个样例的一种可能方案如下：

图1