p03553 AtCoder Regular Contest 085 - MUL
We have N gemstones labeled 1 through N.

You can perform the following operation any number of times (possibly zero).

* Select a positive integer x, and smash all the gems labeled with multiples of x.



Then, for each i, if the gem labeled i remains without getting smashed, you will receive a_i yen (the currency of Japan). However, a_i may be negative, in which case you will be charged money.

By optimally performing the operation, how much yen can you earn?

Constraints

* All input values are integers.
* 1 \leq N \leq 100
* |a_i| \leq 10^9

Input

Input is given from Standard Input in the following format:


N
a_1 a_2 ... a_N


Output

Print the maximum amount of money that can be earned.

Examples

Input

6
1 2 -6 4 5 3


Output

12


Input

6
100 -100 -100 -100 100 -100


Output

200


Input

5
-1 -2 -3 -4 -5


Output

0


Input

2
-1000 100000


Output

99000
```python
def edmonds_karp(s, t, C):
    import copy
    import collections

    r = copy.deepcopy(c)
    maxf = 0

    while True:
        q, found = collections.deque(), False
        q.append(([S], 10 ** 15))
        while len(q) > 0 and not found:
            p, minf = q.popleft()
            for to, flow in r[p[-1]].items():
                if flow == 0:
                    continue
                elif to == T:
                    p, minf = p + [to], min(flow, minf)
                    found = True
                    break
                elif not to in p:
                    q.append((p + [to], min(flow, minf)))

        if not found:
            break

        for i in range(len(p) - 1):
            r[p[i]][p[i + 1]] -= minf
            if p[i] in r[p[i + 1]]:
                r[p[i + 1]][p[i]] += minf
            else:
                r[p[i + 1]][p[i]] = minf
        maxf += minf

    return maxf


N = int(input())
A = list(map(int, input().split()))

gain = sum([max(a, 0) for a in A])

S, T = 0, N + 1
c = [{} for i in range(N + 2)]
for i in range(N):
    ix = i + 1
    if A[i] <= 0:
        c[S][ix] = -A[i]
    else:
        c[ix][T] = A[i]

    for j in range(2 * ix, N + 1, ix):
        c[ix][j] = 10 ** 15

print(gain - edmonds_karp(S, T, c))

```