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.

-----Sample Input-----
6
1 2 -6 4 5 3

-----Sample Output-----
12

It is optimal to smash Gem 3 and 6.

Source: atcoder | Difficulty: HARD


Solutions:
from collections import deque
n = int(input())
a = list(map(int, input().split()))

class Dinic:

	def __init__(self, N):
		self.N = N
		self.G = [[] for i in range(N)]

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.G[fr].append(forward)
		self.G[to].append(backward)

	def add_multi_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.G[v1].append(edge1)
		self.G[v2].append(edge2)

	def bfs(self, s, t):
		self.level = level = [None] * self.N
		deq = deque([s])
		level[s] = 0
		G = self.G
		while deq:
			v = deq.popleft()
			lv = level[v] + 1
			for (w, cap, _) in G[v]:
				if cap and level[w] is None:
					level[w] = lv
					deq.append(w)
		return level[t] is not None

	def dfs(self, v, t, f):
		if v == t:
			return f
		level = self.level
		for e in self.it[v]:
			(w, cap, rev) = e
			if cap and level[v] < level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		INF = 10 ** 9 + 7
		G = self.G
		while self.bfs(s, t):
			(*self.it,) = map(iter, self.G)
			f = INF
			while f:
				f = self.dfs(s, t, INF)
				flow += f
		return flow
graph = Dinic(n + 2)
for i in range(n):
	if a[i] >= 0:
		graph.add_edge(i, n, a[i])
		continue
	graph.add_edge(n + 1, i, -a[i])
for i in range(1, n + 1):
	for j in range(2 * i, n + 1, i):
		graph.add_edge(i - 1, j - 1, 10 ** 11)
print(sum([max(0, i) for i in a]) - graph.flow(n + 1, n))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
from collections import deque

class Dinic:

	def __init__(self, n, edges):
		self.n = n
		self.edges = [[] for _ in range(n)]
		self.iter = [0] * n
		self.level = None
		self.graph(edges)

	def graph(self, E):
		edges = self.edges
		for (fr, to, cap) in E:
			edges[fr].append([to, cap, len(edges[to])])
			edges[to].append([fr, 0, len(edges[fr]) - 1])

	def maxflow(self, source, sink):
		max_flow = 0
		while True:
			self.bfs(source)
			if self.level[sink] < 0:
				return max_flow
			self.iter = [0] * self.n
			flow = self.dfs(source, sink, float('inf'))
			while flow:
				max_flow += flow
				flow = self.dfs(source, sink, float('inf'))

	def bfs(self, source):
		edges = self.edges
		level = [-1] * self.n
		level[source] = 0
		q = deque([source])
		while q:
			fr = q.popleft()
			for (to, cap, _) in edges[fr]:
				if cap > 0 > level[to]:
					level[to] = level[fr] + 1
					q.append(to)
		self.level = level

	def dfs(self, source, sink, flow):
		if source == sink:
			return flow
		while self.iter[source] < len(self.edges[source]):
			(to, cap, rev) = self.edges[source][self.iter[source]]
			if cap > 0 and self.level[source] < self.level[to]:
				f = self.dfs(to, sink, min(flow, cap))
				if f:
					self.edges[source][self.iter[source]][1] -= f
					self.edges[to][rev][1] += f
					return f
			self.iter[source] += 1
		return 0
n = int(input())
A = list(map(int, input().split()))
Edges = []
s = 0
for i in range(n):
	if A[i] <= 0:
		Edges.append((0, i + 1, -A[i]))
	else:
		s += A[i]
		Edges.append((i + 1, n + 1, A[i]))
	for j in range(2 * (i + 1), n + 1, i + 1):
		Edges.append((i + 1, j, float('inf')))
dinic = Dinic(n + 2, Edges)
print(s - dinic.maxflow(0, n + 1))


from collections import deque

def addEdge(adjL, vFr, vTo, cap):
	adjL[vFr].append([vTo, cap, len(adjL[vTo])])
	adjL[vTo].append([vFr, 0, len(adjL[vFr]) - 1])

def Edmonds_Karp(adjL, vSt, vEn):

	def BFS(vSt, vEn):
		prev = [-1] * numV
		prev[vSt] = None
		iE = [-1] * numV
		df = 0
		Q = deque([(vSt, float('inf'))])
		while Q:
			(vNow, fNow) = Q.popleft()
			if vNow == vEn:
				df = fNow
				break
			for (i, (v2, cap, iRev)) in enumerate(adjL[vNow]):
				if prev[v2] == -1 and cap > 0:
					prev[v2] = vNow
					iE[v2] = (i, iRev)
					Q.append((v2, min(fNow, cap)))
		if df > 0:
			vNow = vEn
			while vNow != vSt:
				v0 = prev[vNow]
				(e, iRev) = iE[vNow]
				adjL[v0][e][1] -= df
				adjL[vNow][iRev][1] += df
				vNow = v0
		return df
	numV = len(adjL)
	MaximumFlow = 0
	while True:
		df = BFS(vSt, vEn)
		if df == 0:
			return MaximumFlow
		MaximumFlow += df
N = int(input())
As = list(map(int, input().split()))
adjList = [[] for v in range(N + 2)]
for (i, A) in enumerate(As, 1):
	if A <= 0:
		addEdge(adjList, 0, i, -A)
	else:
		addEdge(adjList, i, N + 1, A)
for i in range(1, N + 1):
	for j in range(2 * i, N + 1, i):
		addEdge(adjList, i, j, float('inf'))
mf = Edmonds_Karp(adjList, 0, N + 1)
print(sum([A for A in As if A > 0]) - mf)


import copy
import collections
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] = 1e+16
r = copy.deepcopy(c)
max_flow = 0
while True:
	(q, s, p) = (collections.deque(), {S}, None)
	q.append((S,))
	findPath = False
	while not len(q) == 0 and (not findPath):
		cand_path = q.popleft()
		for (to, path) in r[cand_path[-1]].items():
			if path == 0:
				continue
			elif to == T:
				p = cand_path + (to,)
				findPath = True
			elif not to in s:
				q.append(cand_path + (to,))
				s.add(to)
	if not findPath:
		break
	min_flow = min([r[p[i]][p[i + 1]] for i in range(len(p) - 1)])
	max_flow += min_flow
	for i in range(len(p) - 1):
		r[p[i]][p[i + 1]] -= min_flow
		if p[i] in r[p[i + 1]]:
			r[p[i + 1]][p[i]] += min_flow
		else:
			r[p[i + 1]][p[i]] = min_flow
print(gain - max_flow)


N = int(input())
P = [int(i) for i in input().split()]
inf = 10 ** 20
table = [[0] * (N + 2) for i in range(N + 2)]
for i in range(1, N + 1):
	if P[i - 1] > 0:
		table[i][N + 1] = P[i - 1]
	else:
		table[0][i] = -P[i - 1]
	for j in range(2 * i, N + 1, i):
		table[i][j] = inf

def fk(x, t, f):
	visit[x] = True
	if x == t:
		return f
	for i in range(N + 2):
		if not visit[i] and table[x][i] > 0:
			df = fk(i, t, min(f, table[x][i]))
			if df > 0:
				table[x][i] -= df
				table[i][x] += df
				return df
	return 0
ans = 0
while True:
	visit = [False] * (N + 2)
	df = fk(0, N + 1, inf)
	if df > 0:
		ans += df
	else:
		break
num = sum([p for p in P if p > 0])
print(num - ans)


from copy import deepcopy
N = int(input())
a0 = list(map(int, input().split()))
for i in range(N, 0, -1):
	if a0[i - 1] < 0:
		tmp = 0
		b = []
		for j in range(1, 101):
			if i * j - 1 >= N:
				break
			tmp += a0[i * j - 1]
			b.append(i * j - 1)
		if tmp < 0:
			for j in b:
				a0[j] = 0
for k1 in range(N, 0, -1):
	for k2 in range(k1 - 1, 0, -1):
		a = deepcopy(a0)
		for j in range(1, 101):
			if k1 * j - 1 >= N:
				break
			a[k1 * j - 1] = 0
		for j in range(1, 101):
			if k2 * j - 1 >= N:
				break
			a[k2 * j - 1] = 0
		for i in range(N, 0, -1):
			if a[i - 1] < 0:
				tmp = 0
				b = []
				for j in range(1, 101):
					if i * j - 1 >= N:
						break
					tmp += a[i * j - 1]
					b.append(i * j - 1)
				if tmp < 0:
					for j in b:
						a[j] = 0
		for i in range(N, 0, -1):
			if a0[i - 1] < 0:
				tmp = 0
				b = []
				for j in range(1, 101):
					if i * j - 1 >= N:
						break
					tmp += a0[i * j - 1]
					b.append(i * j - 1)
				if tmp < 0:
					for j in b:
						a0[j] = 0
		if sum(a) > sum(a0):
			a0 = a
print(sum(a0))


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

def func(Bs):
	for x in range(N):
		if Bs[x] >= 0:
			continue
		if max(Bs[x::x + 1]) <= 0:
			Bs[x] = 0
func(As)
zs = [27, 29, 31, 33] + list(range(34, 51))
for x in zs:
	if sum(As[x - 1::x]) < 0:
		for i in range(x - 1, N, x):
			As[i] = 0
ns = [1, 2, 4, 8, 16, 32] + [3, 6, 9, 12, 18, 24, 27, 36, 48] + [5, 10, 15, 20, 25, 30, 40, 45, 50] + [7, 14, 21, 28, 35, 42, 49] + [11, 22, 33, 44] + [13, 26, 39] + [17, 34] + [19, 38] + [23, 46] + [29, 31, 37, 41, 43, 47]
memo = {}
memo[tuple(As)] = sum(As)
cs = [n - 1 for n in ns if n <= N and n not in zs and (As[n - 1] < 0)]
for c in cs:
	for tupleA in list(memo.keys()):
		if tupleA[c] == 0:
			continue
		listA = list(tupleA)
		for x in range(c, N, c + 1):
			listA[x] = 0
		func(listA)
		memo[tuple(listA)] = sum(listA)
print(max(memo.values()))


import math

def gcd(a, b):
	if a < b:
		(a, b) = (b, a)
	(q, r) = (a, b)
	while r:
		(q, r) = (r, q % r)
	return q

def lcm(a, b):
	return a * b // gcd(a, b)
MAX_N = 102
INF = 10 ** 12
SRC = 0
DST = MAX_N - 1
g = [[0] * MAX_N for _ in range(MAX_N)]
level = []
visited = []
n = 0

def bfs(s):
	nonlocal level
	level = [-1] * MAX_N
	level[s] = 0
	que = [s]
	while 0 < len(que):
		v = que.pop(0)
		for w in range(MAX_N):
			if 0 < g[v][w] and level[w] < 0:
				level[w] = level[v] + 1
				que.append(w)

def dfs(v, t, f):
	nonlocal g, visited
	if v == t:
		return f
	for w in range(visited[v], MAX_N):
		visited[v] = w
		if 0 < g[v][w] and level[v] < level[w]:
			d = dfs(w, t, min(f, g[v][w]))
			if 0 < d:
				g[v][w] -= d
				g[w][v] += d
				return d
	return 0

def max_flow():
	nonlocal visited
	flow = 0
	while True:
		bfs(SRC)
		if level[DST] < 0:
			return flow
		visited = [0] * MAX_N
		f = dfs(SRC, DST, INF)
		while 0 < f:
			flow += f
			f = dfs(SRC, DST, INF)

def solve(n, a):
	nonlocal g
	sum_positive = sum([v for v in a if 0 < v])
	for i in range(1, n + 1):
		if 0 < a[i]:
			g[SRC][i] = a[i]
		elif a[i] < 0:
			g[i][DST] = -a[i]
			for j in range(i * 2, n + 1, i):
				if 0 < a[j]:
					g[j][i] = INF
	return sum_positive - max_flow()

def main():
	nonlocal n
	n = int(input())
	a = list(map(int, input().split()))
	a = [0] + a
	print(solve(n, a))

def __starting_point():
	main()
__starting_point()


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return list(map(int, input().split()))

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class Dinic:
	INF = 10 ** 18

	def __init__(self, n):
		self.n = n
		self.links = [[] for _ in range(n)]
		self.depth = None
		self.progress = None

	def add_link(self, _from, to, cap):
		self.links[_from].append([cap, to, len(self.links[to])])
		self.links[to].append([0, _from, len(self.links[_from]) - 1])

	def bfs(self, s):
		from collections import deque
		depth = [-1] * self.n
		depth[s] = 0
		q = deque([s])
		while q:
			v = q.popleft()
			for (cap, to, _) in self.links[v]:
				if cap > 0 and depth[to] < 0:
					depth[to] = depth[v] + 1
					q.append(to)
		self.depth = depth

	def dfs(self, v, t, flow):
		if v == t:
			return flow
		links_v = self.links[v]
		for i in range(self.progress[v], len(links_v)):
			self.progress[v] = i
			(cap, to, rev) = link = links_v[i]
			if cap == 0 or self.depth[v] >= self.depth[to]:
				continue
			d = self.dfs(to, t, min(flow, cap))
			if d == 0:
				continue
			link[0] -= d
			self.links[to][rev][0] += d
			return d
		return 0

	def max_flow(self, s, t):
		INF = Dinic.INF
		flow = 0
		while True:
			self.bfs(s)
			if self.depth[t] < 0:
				return flow
			self.progress = [0] * self.n
			current_flow = self.dfs(s, t, INF)
			while current_flow > 0:
				flow += current_flow
				current_flow = self.dfs(s, t, INF)
N = INT()
A = LIST()
dinic = Dinic(N + 2)
s = N
t = N + 1
total = 0
for (i, a) in enumerate(A):
	if a < 0:
		dinic.add_link(s, i, -a)
	elif a > 0:
		dinic.add_link(i, t, a)
		total += a
for i in range(1, N + 1):
	j = i
	while j <= N:
		dinic.add_link(i - 1, j - 1, INF)
		j += i
res = dinic.max_flow(s, t)
print(total - res)


import collections

class Dinic:

	def __init__(self, vnum):
		self.edge = [[] for i in range(vnum)]
		self.n = vnum
		self.inf = float('inf')

	def addedge(self, st, en, c):
		self.edge[st].append([en, c, len(self.edge[en])])
		self.edge[en].append([st, 0, len(self.edge[st]) - 1])

	def bfs(self, vst):
		dist = [-1] * self.n
		dist[vst] = 0
		Q = collections.deque([vst])
		while Q:
			nv = Q.popleft()
			for (vt, c, r) in self.edge[nv]:
				if dist[vt] == -1 and c > 0:
					dist[vt] = dist[nv] + 1
					Q.append(vt)
		self.dist = dist

	def dfs(self, nv, en, nf):
		nextv = self.nextv
		if nv == en:
			return nf
		dist = self.dist
		ist = nextv[nv]
		for (i, (vt, c, r)) in enumerate(self.edge[nv][ist:], ist):
			if dist[nv] < dist[vt] and c > 0:
				df = self.dfs(vt, en, min(nf, c))
				if df > 0:
					self.edge[nv][i][1] -= df
					self.edge[vt][r][1] += df
					return df
			nextv[nv] += 1
		return 0

	def getmf(self, st, en):
		mf = 0
		while True:
			self.bfs(st)
			if self.dist[en] == -1:
				break
			self.nextv = [0] * self.n
			while True:
				fl = self.dfs(st, en, self.inf)
				if fl > 0:
					mf += fl
				else:
					break
		return mf

def inpl():
	return [int(i) for i in input().split()]
N = int(input())
a = inpl()
K = Dinic(N + 2)
inf = float('inf')
for (i, v) in enumerate(a, 1):
	if v > 0:
		K.addedge(i, N + 1, v)
	else:
		K.addedge(0, i, -v)
for i in range(1, N + 1):
	for j in range(2 * i, N + 1, i):
		K.addedge(i, j, inf)
print(sum([i for i in a if i > 0]) - K.getmf(0, N + 1))


from collections import defaultdict
from collections import deque

def Ford_Fulkerson_Func(s, g, lines, cost):
	N = len(cost)
	ans = 0
	queue = deque([[s, float('inf')]])
	ed = [True] * N
	ed[s] = False
	route = [0] * N
	route[s] = -1
	while queue:
		(now, flow) = queue.pop()
		for nex in lines[now]:
			if ed[nex]:
				flow = min(cost[now][nex], flow)
				route[nex] = now
				queue.append([nex, flow])
				ed[nex] = False
				if nex == g:
					ans += flow
					break
		else:
			continue
		break
	else:
		return (False, ans)
	t = g
	s = route[t]
	while s != -1:
		cost[s][t] -= flow
		if cost[s][t] == 0:
			lines[s].remove(t)
		if cost[t][s] == 0:
			lines[t].add(s)
		cost[t][s] += flow
		t = s
		s = route[t]
	return (True, ans)

def Ford_Fulkerson(s, g, lines, cost):
	ans = 0
	while True:
		(fl, nans) = Ford_Fulkerson_Func(s, g, lines, cost)
		if fl:
			ans += nans
			continue
		else:
			break
	return ans
N = int(input())
a = list(map(int, input().split()))
S = N + 1
T = N + 2
lis = defaultdict(set)
cost = [[0] * (N + 3) for i in range(N + 3)]
for i in range(N):
	if a[i] > 0:
		lis[i + 1].add(T)
		cost[i + 1][T] += a[i]
	elif a[i] < 0:
		lis[S].add(i + 1)
		cost[S][i + 1] -= a[i]
for i in range(1, N + 1):
	for j in range(i * 2, N + 1, i):
		lis[i].add(j)
		cost[i][j] += float('inf')
m = Ford_Fulkerson(S, T, lis, cost)
ss = 0
for i in range(N):
	if a[i] > 0:
		ss += a[i]
print(ss - m)


from collections import *
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

class Dinic:

	def __init__(self, n, s, t):
		(self.n, self.s, self.t) = (n, s, t)
		self.to = defaultdict(list)
		self.level = [-1]
		self.max_flow = -1

	def add_edge(self, u, v, cap):
		u_index_in_to_v = len(self.to[v])
		v_index_in_to_u = len(self.to[u])
		self.to[u].append([v, cap, u_index_in_to_v])
		self.to[v].append([u, 0, v_index_in_to_u])

	def set_level(self):
		s = self.s
		level = [-1] * self.n
		level[s] = 0
		q = deque()
		q.append([s, 0])
		while q:
			(u, u_level) = q.popleft()
			for (v, cap, _) in self.to[u]:
				if cap == 0:
					continue
				if level[v] != -1:
					continue
				level[v] = u_level + 1
				if v == self.t:
					self.level = level
					return True
				q.append([v, u_level + 1])
		return False

	def dfs(self, u=-1, flow_to_me=10 ** 16):
		if u == -1:
			u = self.s
		if u == self.t:
			return flow_to_me
		flow_from_me = 0
		u_level = self.level[u]
		for (utov_i, (v, cap, vtou_i)) in enumerate(self.to[u]):
			if self.level[v] != u_level + 1:
				continue
			if cap == 0:
				continue
			flow_to_v = self.dfs(v, min(cap, flow_to_me - flow_from_me))
			if not flow_to_v:
				continue
			flow_from_me += flow_to_v
			self.to[u][utov_i][1] -= flow_to_v
			self.to[v][vtou_i][1] += flow_to_v
		return flow_from_me

	def calculation(self):
		res = 0
		while self.set_level():
			res += self.dfs()
		return res

	def get_max_flow(self):
		if self.max_flow == -1:
			self.max_flow = self.calculation()
		return self.max_flow

def main():
	n = int(input())
	aa = LI()
	mf = Dinic(n + 2, 0, n + 1)
	max_sum = 0
	for (i, a) in enumerate(aa, 1):
		if a > 0:
			mf.add_edge(i, n + 1, a)
			max_sum += a
		else:
			mf.add_edge(0, i, -a)
	for i in range(1, n // 2 + 1):
		for j in range(i * 2, n + 1, i):
			mf.add_edge(i, j, 10 ** 12)
	print(max(0, max_sum - mf.get_max_flow()))
main()


import networkx as nx
N = int(input())
(*A,) = map(int, input().split())
INF = 10 ** 20
G = nx.DiGraph()
G.add_nodes_from(range(N + 2))
for i in range(N):
	if A[i] < 0:
		G.add_edge(0, i + 1, capacity=-A[i])
		G.add_edge(i + 1, N + 1, capacity=0)
	else:
		G.add_edge(0, i + 1, capacity=0)
		G.add_edge(i + 1, N + 1, capacity=A[i])
for i in range(1, N // 2 + 1):
	for j in range(i, N + 1, i):
		G.add_edge(i, j, capacity=INF)
(flow_value, flow_dict) = nx.maximum_flow(G, 0, N + 1)
print(sum(filter(lambda x: x > 0, A)) - flow_value)


from collections import deque

def addEdge(adjL, vFr, vTo, cap):
	adjL[vFr].append([vTo, cap, len(adjL[vTo])])
	adjL[vTo].append([vFr, 0, len(adjL[vFr]) - 1])

def Dinic(adjL, vSt, vEn):

	def BFS(vSt):
		dist[vSt] = 0
		Q = deque([vSt])
		while Q:
			vNow = Q.popleft()
			for (i, (v2, cap, iRev)) in enumerate(adjL[vNow]):
				if dist[v2] == -1 and cap > 0:
					dist[v2] = dist[vNow] + 1
					Q.append(v2)

	def DFS(vNow, vEn, fNow):
		if vNow == vEn:
			return fNow
		iSt = iNext[vNow]
		for (i, (v2, cap, iRev)) in enumerate(adjL[vNow][iSt:], iSt):
			if dist[vNow] < dist[v2] and cap > 0:
				df = DFS(v2, vEn, min(fNow, cap))
				if df > 0:
					adjL[vNow][i][1] -= df
					adjL[v2][iRev][1] += df
					return df
			iNext[vNow] += 1
		return 0
	numV = len(adjL)
	MaximumFlow = 0
	while True:
		dist = [-1] * numV
		BFS(vSt)
		if dist[vEn] == -1:
			return MaximumFlow
		iNext = [0] * numV
		while True:
			df = DFS(vSt, vEn, float('inf'))
			if df == 0:
				break
			MaximumFlow += df
N = int(input())
As = list(map(int, input().split()))
adjList = [[] for v in range(N + 2)]
for (i, A) in enumerate(As, 1):
	if A <= 0:
		addEdge(adjList, 0, i, -A)
	else:
		addEdge(adjList, i, N + 1, A)
for i in range(1, N + 1):
	for j in range(2 * i, N + 1, i):
		addEdge(adjList, i, j, float('inf'))
mf = Dinic(adjList, 0, N + 1)
print(sum([A for A in As if A > 0]) - mf)


def addEdge(adjL, vFr, vTo, cap):
	adjL[vFr].append([vTo, cap, len(adjL[vTo])])
	adjL[vTo].append([vFr, 0, len(adjL[vFr]) - 1])

def Ford_Fulkerson(adjL, vSt, vEn):

	def DFS(vNow, vEn, fNow):
		if vNow == vEn:
			return fNow
		used[vNow] = True
		for (i, (v2, cap, iRev)) in enumerate(adjL[vNow]):
			if not used[v2] and cap > 0:
				df = DFS(v2, vEn, min(fNow, cap))
				if df > 0:
					adjL[vNow][i][1] -= df
					adjL[v2][iRev][1] += df
					return df
		return 0
	numV = len(adjL)
	MaximumFlow = 0
	while True:
		used = [False] * numV
		df = DFS(vSt, vEn, float('inf'))
		if df == 0:
			return MaximumFlow
		MaximumFlow += df
N = int(input())
As = list(map(int, input().split()))
adjList = [[] for v in range(N + 2)]
for (i, A) in enumerate(As, 1):
	if A <= 0:
		addEdge(adjList, 0, i, -A)
	else:
		addEdge(adjList, i, N + 1, A)
for i in range(1, N + 1):
	for j in range(2 * i, N + 1, i):
		addEdge(adjList, i, j, float('inf'))
mf = Ford_Fulkerson(adjList, 0, N + 1)
print(sum([A for A in As if A > 0]) - mf)


N = int(input())
alist = [0] + list(map(int, input().split()))
xlist = list(range(1, N + 1))

class FordFulkerson:

	def __init__(self, vlist):
		self.G = {}
		for v in vlist:
			self.G[v] = []

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.G[fr].append(forward)
		self.G[to].append(backward)

	def add_multi_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.G[v1].append(edge1)
		self.G[v2].append(edge2)

	def dfs(self, v, t, f):
		if v == t:
			return f
		used = self.used
		used[v] = True
		for e in self.G[v]:
			(w, cap, rev) = e
			if cap and (not used[w]):
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		f = INF = 10 ** 9 + 7
		while f:
			self.used = {}
			for v in self.G:
				self.used[v] = False
			f = self.dfs(s, t, INF)
			flow += f
		return flow
asum_pos = 0
ff = FordFulkerson(range(N + 2))
for i in range(1, N + 1):
	a = alist[i]
	if a <= 0:
		ff.add_edge(0, i, -a)
	else:
		ff.add_edge(i, N + 1, a)
		asum_pos += a
for i in range(1, N + 1):
	for j in range(2 * i, N + 1, i):
		ff.add_edge(i, j, float('inf'))
penalty = ff.flow(0, N + 1)
print(asum_pos - penalty)


import copy
import queue
N = int(input())
a_list = list(map(int, input().split()))
gain = sum([a for a in a_list if a > 0])
S = 0
T = N + 1
c = [{} for i in range(N + 2)]
for (i, a) in enumerate(a_list):
	index = i + 1
	if a <= 0:
		c[S][index] = -a
	else:
		c[index][T] = a
	for j in range(index, N + 1, index):
		if not j == index:
			c[index][j] = 1e+16
r = copy.deepcopy(c)
max_flow = 0
while True:
	(q, s, p) = (queue.Queue(), {S}, None)
	q.put((S,))
	findPath = False
	while not q.empty() and (not findPath):
		cand_path = q.get(False)
		for (to, path) in list(r[cand_path[-1]].items()):
			if path == 0:
				continue
			elif to == T:
				p = cand_path + (to,)
				findPath = True
			elif not to in s:
				q.put(cand_path + (to,))
				s.add(to)
	if not findPath:
		break
	min_flow = min([r[p[i]][p[i + 1]] for i in range(len(p) - 1)])
	max_flow += min_flow
	for i in range(len(p) - 1):
		r[p[i]][p[i + 1]] -= min_flow
		if p[i] in r[p[i + 1]]:
			r[p[i + 1]][p[i]] += min_flow
		else:
			r[p[i + 1]][p[i]] = min_flow
print(gain - max_flow)


from scipy.sparse.csgraph import dijkstra
import numpy as np
n = int(input())
a = [0] + [int(j) for j in input().split()]
graph = np.zeros((n + 2, n + 2), dtype=np.int64)
(start, goal) = (0, n + 1)
for (i, j) in enumerate(a[1:], 1):
	if j >= 0:
		graph[start, i] = j
	else:
		graph[i, goal] = -j
for i in range(1, n + 1):
	for j in range(2 * i, n + 1, i):
		graph[j, i] = 10 ** 18

def max_flow(graph):
	flow = 0
	while True:
		(dist, pred) = dijkstra(graph, indices=start, return_predecessors=True, unweighted=True)
		if dist[goal] == np.inf:
			return flow
		path = []
		v = goal
		while True:
			path.append((pred[v], v))
			v = pred[v]
			if v == start:
				break
		add_flow = min((graph[x][y] for (x, y) in path))
		for (x, y) in path:
			graph[x][y] -= add_flow
			graph[y][x] += add_flow
		flow += add_flow
print(sum((i for i in a if i > 0)) - max_flow(graph))


class Dinic:

	def __init__(self, v, inf=float('inf')):
		self.V = v
		self.inf = inf
		self.G = [[] for _ in range(v)]
		self.level = [0 for _ in range(v)]
		self.iter = [0 for _ in range(v)]

	def addEdge(self, fm, to, cap):
		self.G[fm].append({'to': to, 'cap': cap, 'rev': len(self.G[to])})
		self.G[to].append({'to': fm, 'cap': 0, 'rev': len(self.G[fm]) - 1})

	def bfs(self, s):
		import queue
		self.level = [-1 for _ in range(self.V)]
		self.level[s] = 0
		que = queue.Queue()
		que.put(s)
		while not que.empty():
			v = que.get()
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if e['cap'] > 0 and self.level[e['to']] < 0:
					self.level[e['to']] = self.level[v] + 1
					que.put(e['to'])

	def dfs(self, v, t, f):
		if v == t:
			return f
		for i in range(self.iter[v], len(self.G[v])):
			self.iter[v] = i
			e = self.G[v][i]
			if e['cap'] > 0 and self.level[v] < self.level[e['to']]:
				d = self.dfs(e['to'], t, min(f, e['cap']))
				if d > 0:
					e['cap'] -= d
					self.G[e['to']][e['rev']]['cap'] += d
					return d
		return 0

	def max_flow(self, s, t):
		flow = 0
		while True:
			self.bfs(s)
			if self.level[t] < 0:
				return flow
			self.iter = [0 for _ in range(self.V)]
			f = self.dfs(s, t, self.inf)
			while f > 0:
				flow += f
				f = self.dfs(s, t, self.inf)
from sys import stdin, setrecursionlimit

def IL():
	return list(map(int, stdin.readline().split()))
setrecursionlimit(1000000)

def main():
	N = int(input())
	a = IL()
	d = Dinic(N + 2)
	res = 0
	for i in range(N):
		d.addEdge(N, i, max(0, -a[i]))
		d.addEdge(i, N + 1, max(0, a[i]))
		res += max(0, a[i])
		t = 2 * i + 2
		while t <= N:
			d.addEdge(i, t - 1, float('inf'))
			t += i + 1
	print(res - d.max_flow(N, N + 1))
main()


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
sys.setrecursionlimit(2147483647)
INF = 10 ** 20

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

class Dinic:

	def __init__(self, source, sink):
		self.G = defaultdict(lambda : defaultdict(int))
		self.sink = sink
		self.source = source

	def add_edge(self, u, v, cap):
		self.G[u][v] = cap
		self.G[v][u] = 0

	def bfs(self):
		level = defaultdict(int)
		q = [self.source]
		level[self.source] = 1
		d = 1
		while q:
			if level[self.sink]:
				break
			qq = []
			d += 1
			for u in q:
				for (v, cap) in self.G[u].items():
					if cap == 0:
						continue
					if level[v]:
						continue
					level[v] = d
					qq += [v]
			q = qq
		self.level = level

	def dfs(self, u, f):
		if u == self.sink:
			return f
		for (v, cap) in self.iter[u]:
			if cap == 0 or self.level[v] != self.level[u] + 1:
				continue
			d = self.dfs(v, min(f, cap))
			if d:
				self.G[u][v] -= d
				self.G[v][u] += d
				return d
		return 0

	def max_flow(self):
		flow = 0
		while True:
			self.bfs()
			if self.level[self.sink] == 0:
				break
			self.iter = {u: iter(self.G[u].items()) for u in self.G}
			while True:
				f = self.dfs(self.source, INF)
				if f == 0:
					break
				flow += f
		return flow
n = I()
s = 0
t = n + 1
dinic = Dinic(s, t)
A = LI()
total = 0
for i in range(1, n + 1):
	if A[i - 1] >= 0:
		total += A[i - 1]
		dinic.add_edge(s, i, 0)
		dinic.add_edge(i, t, A[i - 1])
	else:
		dinic.add_edge(s, i, -A[i - 1])
		dinic.add_edge(i, t, 0)
	for j in range(i * 2, n + 1, i):
		dinic.add_edge(i, j, INF)
print(total - dinic.max_flow())


from collections import deque

class Dinic:

	def __init__(self, v, inf=10 ** 9 + 7):
		self.V = v
		self.inf = inf
		self.G = [list() for _ in range(v)]
		self.level = [-1 for _ in range(v)]
		self.iter = [0] * v

	def addedge(self, fr, to, cap):
		go = [to, cap, None]
		go[2] = back = [fr, 0, go]
		self.G[fr].append(go)
		self.G[to].append(back)

	def bfs(self, st, en):
		q = deque([st])
		self.level = [-1 for _ in range(self.V)]
		self.level[st] = 0
		while q:
			cur = q.popleft()
			for (x, cap, _) in self.G[cur]:
				if cap and self.level[x] < 0:
					self.level[x] = self.level[cur] + 1
					q.append(x)
		return self.level[en] > 0

	def dfs(self, v, t, f):
		if v == t:
			return f
		for e in self.iter[v]:
			(w, cap, rev) = e
			if cap and self.level[v] < self.level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		while self.bfs(s, t):
			self.iter = list(map(iter, self.G))
			f = self.dfs(s, t, self.inf)
			while f:
				flow += f
				f = self.dfs(s, t, self.inf)
		return flow

def main():
	n = int(input())
	a = list(map(int, input().split()))
	D = Dinic(n + 2)
	ret = 0
	for (i, e) in enumerate(a, 1):
		if e > 0:
			ret += e
			D.addedge(i, n + 1, e)
		else:
			D.addedge(0, i, -e)
	for i in range(1, n // 2 + 1):
		for j in range(i * 2, n + 1, i):
			D.addedge(i, j, 10 ** 12)
	loss = D.flow(0, n + 1)
	return ret - loss
print(main())


from sys import stdin
from fractions import gcd
from functools import reduce

def lcm(x, y):
	return x * (y // gcd(x, y))

def flatten(ls):
	return [x for l in ls for x in l]

def multiples(t, N):
	return set((i for x in t for i in range(x, N + 1, x)))

def value(a, t):
	return sum((a[i - 1] for i in multiples(t, len(a))))

def remove(a, t):
	for i in multiples(t, len(a)):
		a[i - 1] = 0

def tuples(m, N):
	if m == 0:
		return [[()]]
	ts = tuples(m - 1, N)
	if ts[-1] == []:
		return ts
	ls = []
	for t in ts[-1]:
		lc = reduce(lcm, t) if len(t) > 0 else 1
		mi = min(t) if len(t) > 0 else N + 1
		for i in range(mi - 1, 0, -1):
			if lcm(lc, i) > N:
				continue
			if any((j % i == 0 for j in t)):
				continue
			ls.append((i,) + t)
	ts.append(ls)
	return ts

def solve(a):
	N = len(a)
	tl = flatten(tuples(N, N))
	tl.sort(key=lambda t: [-x for x in t])
	for t in tl:
		if value(a, t) < 0:
			remove(a, t)
	return sum(a)
N = int(stdin.readline())
a = [int(w) for w in stdin.readline().split()]
if len(a) != N:
	raise
print(solve(a))


from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def A():
	return

def B():
	return

def C():

	def bfs(s, g, n):
		bfs_map = [-1 for i in range(n)]
		bfs_map[s] = 0
		q = deque()
		q.append(s)
		fin = False
		while q:
			x = q.popleft()
			for y in range(n):
				if c[x][y] > 0 and bfs_map[y] < 0:
					bfs_map[y] = bfs_map[x] + 1
					if y == g:
						fin = True
						break
					q.append(y)
			if fin:
				break
		if bfs_map[g] == -1:
			return (None, 0)
		path = [None] * (bfs_map[g] + 1)
		m = float('inf')
		path[bfs_map[g]] = g
		y = g
		for i in range(bfs_map[g])[::-1]:
			for x in range(n):
				if c[x][y] > 0 and bfs_map[x] == bfs_map[y] - 1:
					path[i] = x
					if c[x][y] < m:
						m = c[x][y]
					y = x
					break
		return (path, m)

	def ford_fulkerson(s, g, c, n):
		f = 0
		while 1:
			(p, m) = bfs(s, g, n)
			if not m:
				break
			f += m
			for i in range(len(p) - 1):
				c[p[i]][p[i + 1]] -= m
				c[p[i + 1]][p[i]] += m
		return f
	n = I()
	a = LI()
	e = n + 2
	ma = 10 ** 9
	c = [[0] * e for i in range(e)]
	for i in range(n):
		d = i + 1
		j = 2 * d
		c[0][d] = ma
		c[d][n + 1] = ma - a[i]
		while j <= n:
			c[j][d] = float('inf')
			j += d
	print(ma * n - ford_fulkerson(0, n + 1, c, e))
	return

def D():
	return

def E():
	return

def F():
	return

def __starting_point():
	C()
__starting_point()


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))


from collections import deque
N = int(input())
A = list(map(int, input().split()))
P = N + 2
es = [[] for i in range(P)]

def add_edge(fr, to, cap):
	es[fr].append([to, cap, len(es[to])])
	es[to].append([fr, 0, len(es[fr]) - 1])
INF = float('inf')
score = 0
for (i, a) in enumerate(A):
	if a > 0:
		add_edge(0, i + 1, a)
		score += a
	elif a < 0:
		add_edge(i + 1, N + 1, -a)
for n in range(1, N // 2 + 1):
	for m in range(2 * n, N + 1, n):
		add_edge(m, n, INF)
level = [0] * P
iters = [0] * P

def dinic_max_flow(s, t):
	global iters

	def _bfs(s):
		global level
		level = [-1] * P
		level[s] = 0
		q = deque([s])
		while q:
			v = q.popleft()
			for (to, cap, rev) in es[v]:
				if cap > 0 and level[to] < 0:
					level[to] = level[v] + 1
					q.append(to)

	def _dfs(v, t, f):
		if v == t:
			return f
		for i in range(iters[v], len(es[v])):
			iters[v] += 1
			(to, cap, rev) = es[v][i]
			if es[v][i][1] > 0 and level[v] < level[to]:
				d = _dfs(to, t, min(f, es[v][i][1]))
				if d > 0:
					es[v][i][1] -= d
					es[to][rev][1] += d
					return d
		return 0
	flow = 0
	while True:
		_bfs(s)
		if level[t] < 0:
			return flow
		iters = [0] * P
		f = 0
		while True:
			f = _dfs(s, t, INF)
			if f <= 0:
				break
			flow += f
print(score - dinic_max_flow(0, N + 1))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))
from collections import deque
MAX_V = 100000
G = [[] for _ in range(MAX_V)]
level = [0 for _ in range(MAX_V)]
iter = [0 for _ in range(MAX_V)]

def add_edge(fr, to, cp):
	G[fr].append((to, cp, len(G[to])))
	G[to].append((fr, 0, len(G[fr]) - 1))

def bfs(s):
	for i in range(MAX_V):
		level[i] = -1
	que = deque()
	level[s] = 0
	que.append(s)
	while len(que) != 0:
		v = que.popleft()
		for e in G[v]:
			if e[1] > 0 and level[e[0]] < 0:
				level[e[0]] = level[v] + 1
				que.append(e[0])

def dfs(v, t, f):
	if v == t:
		return f
	for i in range(iter[v], len(G[v])):
		if G[v][i][1] > 0 and level[v] < level[G[v][i][0]]:
			d = dfs(G[v][i][0], t, min(G[v][i][1], f))
			if d > 0:
				G[v][i] = (G[v][i][0], G[v][i][1] - d, G[v][i][2])
				G[G[v][i][0]][G[v][i][2]] = (G[G[v][i][0]][G[v][i][2]][0], G[G[v][i][0]][G[v][i][2]][1] + d, G[G[v][i][0]][G[v][i][2]][2])
				return d
	return 0

def max_flow(s, t, FLW_LIM=10 ** 18):
	flow = 0
	while True:
		bfs(s)
		if level[t] < 0:
			return flow
		for i in range(MAX_V):
			iter[i] = 0
		f = 0
		while True:
			f = dfs(s, t, FLW_LIM)
			if f == 0:
				break
			flow += f

def main():
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(1, n + 1):
		for j in range(i, n + 1, i):
			add_edge(i, j, 10 ** 18 + 5)
	for (i, _a) in enumerate(a):
		if _a < 0:
			add_edge(0, i + 1, -_a)
		else:
			add_edge(i + 1, n + 1, _a)
	ans = 0
	for _a in a:
		if _a > 0:
			ans += _a
	print(ans - max_flow(0, n + 1))
main()


import sys
input = sys.stdin.readline
from scipy.sparse.csgraph import dijkstra
import numpy as np
N = int(input())
start = 0
goal = N + 1
A = [0] + [int(x) for x in input().split()]
INF = 10 ** 12
graph = np.zeros((N + 2, N + 2), dtype=np.int64)
for (i, a) in enumerate(A[1:], 1):
	if a >= 0:
		graph[start, i] = a
	else:
		graph[i, goal] = -a
for i in range(1, N + 1):
	for j in range(2 * i, N + 1, i):
		if A[i] < 0 and A[j] > 0:
			graph[j][i] = INF

def max_flow(graph):
	flow = 0
	while True:
		(dist, pred) = dijkstra(graph, indices=start, return_predecessors=True, unweighted=True)
		if dist[goal] == np.inf:
			return flow
		path = []
		v = goal
		while True:
			path.append((pred[v], v))
			v = pred[v]
			if v == start:
				break
		add_flow = min((graph[x][y] for (x, y) in path))
		for (x, y) in path:
			graph[x][y] -= add_flow
			graph[y][x] += add_flow
		flow += add_flow
answer = sum((x for x in A if x > 0)) - max_flow(graph)
print(answer)


import networkx as nx
n = int(input())
A = list(map(int, input().split()))
G = nx.DiGraph()
source = 'source'
sink = 'sink'
for i in range(1, n + 1):
	(x, y) = (A[i - 1], 0)
	if A[i - 1] < 0:
		(x, y) = (y, -x)
	G.add_edge(source, i, capacity=x)
	G.add_edge(i, sink, capacity=y)
for i in range(1, n // 2 + 1):
	for j in range(2 * i, n + 1, i):
		G.add_edge(j, i)
try:
	(mincut, cut_dic) = nx.minimum_cut(G, source, sink)
	res = sum((a for a in A if a > 0))
	print(res - mincut)
except nx.NetworkXError:
	print(0)


from collections import deque

class Dinic:

	def __init__(self, N):
		self.N = N
		self.G = [[] for i in range(N)]

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.G[fr].append(forward)
		self.G[to].append(backward)

	def add_multi_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.G[v1].append(edge1)
		self.G[v2].append(edge2)

	def bfs(self, s, t):
		self.level = level = [None] * self.N
		deq = deque([s])
		level[s] = 0
		G = self.G
		while deq:
			v = deq.popleft()
			lv = level[v] + 1
			for (w, cap, _) in G[v]:
				if cap and level[w] is None:
					level[w] = lv
					deq.append(w)
		return level[t] is not None

	def dfs(self, v, t, f):
		if v == t:
			return f
		level = self.level
		for e in self.it[v]:
			(w, cap, rev) = e
			if cap and level[v] < level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		INF = 10 ** 9 + 7
		G = self.G
		while self.bfs(s, t):
			(*self.it,) = map(iter, self.G)
			f = INF
			while f:
				f = self.dfs(s, t, INF)
				flow += f
		return flow
N = int(input())
a = list(map(int, input().split()))
D = Dinic(N + 2)
inf = 10 ** 18
profit = 0
cost = 0
for i in range(N):
	if a[i] >= 0:
		D.add_edge(i, N + 1, a[i])
	else:
		D.add_edge(N, i, -a[i])
		cost += a[i]
	profit += abs(a[i])
for i in range(1, N + 1):
	for k in range(2, N // i + 1):
		D.add_edge(i - 1, i * k - 1, inf)
f = D.flow(N, N + 1)
print(profit - f + cost)


import collections

class MaxFlow:

	class Edge:

		def __init__(self, to, cap, rev):
			(self.to, self.cap, self.rev) = (to, cap, rev)

	def __init__(self, V):
		self.V = V
		self.E = [[] for _ in range(V)]

	def add_edge(self, fr, to, cap):
		self.E[fr].append(self.Edge(to, cap, len(self.E[to])))
		self.E[to].append(self.Edge(fr, 0, len(self.E[fr]) - 1))

	def dinic(self, source, sink, INF=10 ** 9):
		maxflow = 0
		while True:
			self.bfs(source)
			if self.level[sink] < 0:
				return maxflow
			self.itr = [0] * self.V
			while True:
				flow = self.dfs(source, sink, INF)
				if flow > 0:
					maxflow += flow
				else:
					break

	def dfs(self, vertex, sink, flow):
		if vertex == sink:
			return flow
		for i in range(self.itr[vertex], len(self.E[vertex])):
			self.itr[vertex] = i
			e = self.E[vertex][i]
			if e.cap > 0 and self.level[vertex] < self.level[e.to]:
				d = self.dfs(e.to, sink, min(flow, e.cap))
				if d > 0:
					e.cap -= d
					self.E[e.to][e.rev].cap += d
					return d
		return 0

	def bfs(self, start):
		que = collections.deque()
		self.level = [-1] * self.V
		que.append(start)
		self.level[start] = 0
		while que:
			fr = que.popleft()
			for e in self.E[fr]:
				if e.cap > 0 and self.level[e.to] < 0:
					self.level[e.to] = self.level[fr] + 1
					que.append(e.to)

def main():
	INF = 10 ** 9
	N = int(input())
	A = [int(x) for x in input().split()]
	flow = MaxFlow(N + 2)
	(source, sink) = (N, N + 1)
	for (i, a) in enumerate(A):
		if a >= 0:
			flow.add_edge(source, i, a)
		else:
			flow.add_edge(i, sink, abs(a))
	for i in range(1, N + 1):
		for j in range(i, N + 1):
			if j % i == 0:
				flow.add_edge(j - 1, i - 1, INF)
	cost = flow.dinic(source, sink, INF)
	print(sum((a for a in A if a > 0)) - cost)

def __starting_point():
	main()
__starting_point()


from collections import deque

class Dinic:

	def __init__(self, number):
		self.table = [[0] * number for i in range(number)]
		self.n = number

	def add(self, x, y, f):
		self.table[x][y] = f

	def bfs(self, x):
		self.visit[x] = 0
		h = deque()
		h.append(x)
		while h:
			y = h.popleft()
			for i in range(self.n):
				if self.visit[i] == -1 and self.table[y][i] > 0:
					self.visit[i] = self.visit[y] + 1
					h.append(i)
		return 0

	def dinic(self, s, t, f):
		if s == t:
			return f
		for i in range(self.n):
			if self.visit[i] > self.visit[s] and self.table[s][i] > 0:
				df = self.dinic(i, t, min(f, self.table[s][i]))
				if df > 0:
					self.table[s][i] -= df
					self.table[i][s] += df
					return df
		return 0

	def flow(self, s, t):
		ans = 0
		inf = 10 ** 20
		while True:
			self.visit = [-1] * self.n
			self.bfs(s)
			if self.visit[t] == -1:
				break
			while True:
				df = self.dinic(s, t, inf)
				if df == 0:
					break
				ans += df
		return ans
N = int(input())
P = [int(i) for i in input().split()]
inf = 10 ** 20
maxflow = Dinic(N + 2)
for i in range(1, N + 1):
	if P[i - 1] > 0:
		maxflow.add(i, N + 1, P[i - 1])
	else:
		maxflow.add(0, i, -P[i - 1])
	for j in range(2 * i, N + 1, i):
		maxflow.add(i, j, inf)
ans = maxflow.flow(0, N + 1)
num = sum([p for p in P if p > 0])
print(num - ans)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque
(N, *A) = map(int, read().split())

class Dinic:

	def __init__(self, N, source, sink):
		self.N = N
		self.G = [[] for _ in range(N)]
		self.source = source
		self.sink = sink

	def add_edge(self, fr, to, cap):
		n1 = len(self.G[fr])
		n2 = len(self.G[to])
		self.G[fr].append([to, cap, n2])
		self.G[to].append([fr, 0, n1])

	def add_edge_undirected(self, fr, to, cap):
		n1 = len(self.G[fr])
		n2 = len(self.G[to])
		self.G[fr].append([to, cap, n2])
		self.G[to].append([fr, cap, n1])

	def bfs(self):
		level = [0] * self.N
		G = self.G
		source = self.source
		sink = self.sink
		q = deque([source])
		level[source] = 1
		pop = q.popleft
		append = q.append
		while q:
			v = pop()
			lv = level[v] + 1
			for (to, cap, rev) in G[v]:
				if not cap:
					continue
				if level[to]:
					continue
				level[to] = lv
				if to == sink:
					self.level = level
					return
				append(to)
		self.level = level

	def dfs(self, v, f):
		if v == self.sink:
			return f
		G = self.G
		prog = self.progress
		level = self.level
		lv = level[v]
		E = G[v]
		for i in range(prog[v], len(E)):
			(to, cap, rev) = E[i]
			prog[v] = i
			if not cap:
				continue
			if level[to] <= lv:
				continue
			x = f if f < cap else cap
			ff = self.dfs(to, x)
			if ff:
				E[i][1] -= ff
				G[to][rev][1] += ff
				return ff
		return 0

	def max_flow(self):
		INF = 10 ** 18
		flow = 0
		while True:
			self.bfs()
			if not self.level[self.sink]:
				return flow
			self.progress = [0] * self.N
			while True:
				f = self.dfs(self.source, INF)
				if not f:
					break
				flow += f
		return flow
source = 0
sink = N + 1
INF = 10 ** 18
dinic = Dinic(N + 2, source, sink)
add = dinic.add_edge
for (i, x) in enumerate(A, 1):
	if x < 0:
		add(source, i, -x)
	else:
		add(i, sink, x)
for i in range(1, N + 1):
	for j in range(i + i, N + 1, i):
		add(i, j, INF)
f = dinic.max_flow()
x = sum((x for x in A if x >= 0))
answer = x - f
print(answer)


INF = float('inf')

def fulkerson(graph, src, sink):
	n = len(graph)
	matrix = [[0] * n for i in range(n)]
	bothDirGraph = [[] for i in range(n)]
	for (nodeId, edges) in enumerate(graph):
		for (nodeId2, flowLimit) in edges:
			matrix[nodeId][nodeId2] = flowLimit
			bothDirGraph[nodeId].append(nodeId2)
			bothDirGraph[nodeId2].append(nodeId)
	while True:
		path = findPath(bothDirGraph, matrix, src, sink)
		if path == None:
			break
		v = min((matrix[path[i]][path[i + 1]] for i in range(len(path) - 1)))
		for i in range(len(path) - 1):
			node1 = path[i]
			node2 = path[i + 1]
			matrix[node1][node2] -= v
			matrix[node2][node1] += v
	return sum((c for (_, c) in graph[src])) - sum((c for c in matrix[src]))

def findPath(bothDirGraph, matrix, src, sink):
	prevs = [None] * len(matrix)
	q = set([src])
	prevs[src] = src
	while len(q) > 0:
		node = q.pop()
		for nextNode in bothDirGraph[node]:
			if prevs[nextNode] == None and matrix[node][nextNode] > 0:
				prevs[nextNode] = node
				if nextNode == sink:
					path = []
					pathNode = sink
					while pathNode != src:
						path.append(pathNode)
						pathNode = prevs[pathNode]
					path.append(src)
					return list(reversed(path))
				q.add(nextNode)
	return None

def f(N, A):
	graph = [[] for i in range(N + 2)]
	srcId = 0
	dstId = N + 1
	for (nodeId, a) in enumerate(A, 1):
		if a < 0:
			graph[0].append((nodeId, -a))
		else:
			graph[nodeId].append((N + 1, a))
		for k in range(2, N // nodeId + 1):
			graph[nodeId].append((nodeId * k, INF))
	return sum(filter(lambda a: a > 0, A)) - fulkerson(graph, 0, N + 1)

def main():
	N = int(input())
	A = list(map(int, input().split()))
	print(f(N, A))
main()


n = int(input())
a = [0] + list(map(int, input().split()))
alive = [1 for i in range(n + 1)]
sol = sum(a)
while True:
	pot = []
	change = False
	for i in range(n, 0, -1):
		if a[i] >= 0 or alive[i] == 0:
			continue
		saldo = 0
		j = i
		while j <= n:
			saldo += alive[j] * a[j]
			j += i
		if saldo > 0:
			pot.append(i)
			continue
		change = True
		sol -= saldo
		j = i
		while j <= n:
			alive[j] = 0
			j += i
	if change:
		continue
	k = len(pot)
	for i in range(k):
		if change:
			break
		for j in range(i):
			saldo = 0
			for v in range(1, n + 1):
				if v % pot[i] == 0 or v % pot[j] == 0:
					saldo += alive[v] * a[v]
			if saldo <= 0:
				change = True
				sol -= saldo
				for v in range(1, n + 1):
					if v % pot[i] == 0 or v % pot[j] == 0:
						alive[v] = 0
				break
	if not change:
		break
print(sol)


from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *

def read():
	return int(input())

def reads():
	return [int(x) for x in input().split()]
INF = 1 << 60

def main():
	N = read()
	A = reads()
	offset = sum((a for a in A if a > 0))
	di = dinic(N + 2)
	for i in range(1, N + 1):
		a = A[i - 1]
		if a <= 0:
			di.add_edge(0, i, -a)
		else:
			di.add_edge(i, N + 1, a)
		for j in range(2 * i, N + 1, i):
			di.add_edge(i, j, INF)
	ans = offset - di.max_flow(0, N + 1)
	print(ans)

class dinic:

	def __init__(self, N):
		self.size = N
		self.edges = [[] for _ in range(N)]

	def add_edge(self, u, v, c):
		self.edges[u].append((v, c))
		self.edges[v].append((u, 0))

	def bfs(self, cap, s):
		N = self.size
		edges = self.edges
		level = [-1] * N
		level[s] = 0
		que = deque([s])
		while len(que) > 0:
			u = que.popleft()
			for (v, _) in edges[u]:
				if cap[u][v] > 0 and level[v] < 0:
					level[v] = level[u] + 1
					que.append(v)
		return level

	def dfs(self, cap, itr, level, u, t, f):
		N = self.size
		edges = self.edges
		if u == t:
			return f
		for i in range(itr[u], len(edges[u])):
			itr[u] = i
			(v, _) = edges[u][i]
			if cap[u][v] > 0 and level[u] < level[v]:
				d = self.dfs(cap, itr, level, v, t, min(f, cap[u][v]))
				if d > 0:
					cap[u][v] -= d
					cap[v][u] += d
					return d
		return 0

	def max_flow(self, s, t):
		N = self.size
		edges = self.edges
		cap = [[0] * N for _ in range(N)]
		for u in range(N):
			for (v, c) in edges[u]:
				cap[u][v] += c
		flow = 0
		while True:
			level = self.bfs(cap, s)
			if level[t] < 0:
				return flow
			itr = [0] * N
			while True:
				f = self.dfs(cap, itr, level, s, t, INF)
				if f <= 0:
					break
				flow += f
main()


from networkx import *
(n, *A) = map(int, open((s := 0)).read().split())
G = DiGraph()
G.add_nodes_from(range(n + 2))
for (i, a) in enumerate(A, 1):
	if a > 0:
		s += a
		G.add_edge(i, n + 1, capacity=a)
	else:
		G.add_edge(0, i, capacity=-a)
	for j in range(i + i, n + 1, i):
		G.add_edge(i, j, capacity=9e+20)
print(s - maximum_flow(G, 0, n + 1)[0])


class Ford_Fulkerson:

	def __init__(self, v, inf=float('inf')):
		self.V = v
		self.inf = inf
		self.G = [[] for _ in range(v)]
		self.used = [False for _ in range(v)]

	def addEdge(self, fm, to, cap):
		self.G[fm].append({'to': to, 'cap': cap, 'rev': len(self.G[to])})
		self.G[to].append({'to': fm, 'cap': 0, 'rev': len(self.G[fm]) - 1})

	def dfs(self, v, t, f):
		if v == t:
			return f
		self.used[v] = True
		for i in range(len(self.G[v])):
			e = self.G[v][i]
			if self.used[e['to']] != True and e['cap'] > 0:
				d = self.dfs(e['to'], t, min(f, e['cap']))
				if d > 0:
					e['cap'] -= d
					self.G[e['to']][e['rev']]['cap'] += d
					return d
		return 0

	def max_flow(self, s, t):
		flow = 0
		while True:
			self.used = [False for i in range(self.V)]
			f = self.dfs(s, t, self.inf)
			if f == 0:
				return flow
			flow += f
from sys import stdin, setrecursionlimit

def IL():
	return list(map(int, stdin.readline().split()))
setrecursionlimit(1000000)

def main():
	N = int(input())
	a = IL()
	d = Ford_Fulkerson(N + 2)
	res = 0
	for i in range(N):
		d.addEdge(N, i, max(0, -a[i]))
		d.addEdge(i, N + 1, max(0, a[i]))
		res += max(0, a[i])
		t = 2 * i + 2
		while t <= N:
			d.addEdge(i, t - 1, float('inf'))
			t += i + 1
	print(res - d.max_flow(N, N + 1))

def __starting_point():
	main()
__starting_point()


import collections

class Dinic:

	def __init__(self, n):
		self.n = n
		self.g = [[] for i in range(n)]

	def add_edge(self, fr, to, cap):
		self.g[fr].append([to, cap, len(self.g[to])])
		self.g[to].append([fr, 0, len(self.g[fr]) - 1])

	def add_multi_edge(self, v1, v2, cap1, cap2):
		self.g[v1].append([v2, cap1, len(self.g[v2])])
		self.g[v2].append([v1, cap2, len(self.g[v1]) - 1])

	def bfs(self, s):
		level = [-1] * self.n
		deq = collections.deque()
		level[s] = 0
		deq.append(s)
		while deq:
			v = deq.popleft()
			for e in self.g[v]:
				if e[1] > 0 and level[e[0]] < 0:
					level[e[0]] = level[v] + 1
					deq.append(e[0])
		self.level = level

	def dfs(self, v, t, f):
		if v == t:
			return f
		es = self.g[v]
		level = self.level
		for i in range(self.it[v], len(self.g[v])):
			e = es[i]
			if e[1] > 0 and level[v] < level[e[0]]:
				d = self.dfs(e[0], t, min(f, e[1]))
				if d > 0:
					e[1] -= d
					self.g[e[0]][e[2]][1] += d
					self.it[v] = i
					return d
		self.it[v] = len(self.g[v])
		return 0

	def max_flow(self, s, t):
		flow = 0
		while True:
			self.bfs(s)
			if self.level[t] < 0:
				break
			self.it = [0] * self.n
			while True:
				f = self.dfs(s, t, 10 ** 9 + 7)
				if f > 0:
					flow += f
				else:
					break
		return flow
N = int(input())
(*A,) = map(int, input().split())
dinic = Dinic(N + 2)
INF = 10 ** 18
su = 0
for x in range(1, N + 1):
	a = A[x - 1]
	if a > 0:
		su += a
		dinic.add_edge(0, x + 1, a)
	elif a < 0:
		dinic.add_edge(x + 1, 1, -a)
for x in range(1, N + 1):
	for y in range(x + x, N + 1, x):
		dinic.add_edge(y + 1, x + 1, INF)
print(su - dinic.max_flow(0, 1))


from collections import deque

class Dinic:

	def __init__(self, n):
		self.n = n
		self.links = [[] for _ in range(n)]
		self.depth = None
		self.progress = None

	def add_link(self, _from, to, cap):
		self.links[_from].append([cap, to, len(self.links[to])])
		self.links[to].append([0, _from, len(self.links[_from]) - 1])

	def bfs(self, s):
		depth = [-1] * self.n
		depth[s] = 0
		q = deque([s])
		while q:
			v = q.popleft()
			for (cap, to, rev) in self.links[v]:
				if cap > 0 and depth[to] < 0:
					depth[to] = depth[v] + 1
					q.append(to)
		self.depth = depth

	def dfs(self, v, t, flow):
		if v == t:
			return flow
		for (i, link) in enumerate(self.links[v]):
			if i < self.progress[v]:
				continue
			self.progress[v] = i
			(cap, to, rev) = link
			if cap == 0 or self.depth[v] >= self.depth[to]:
				continue
			d = self.dfs(to, t, min(flow, cap))
			if d == 0:
				continue
			link[0] -= d
			self.links[to][rev][0] += d
			return d
		return 0

	def max_flow(self, s, t):
		flow = 0
		while True:
			self.bfs(s)
			if self.depth[t] < 0:
				return flow
			self.progress = [0] * self.n
			current_flow = self.dfs(s, t, float('inf'))
			while current_flow > 0:
				flow += current_flow
				current_flow = self.dfs(s, t, float('inf'))
n = int(input())
an = list(map(int, input().split()))
mf = Dinic(n + 2)
max_value = 0
for (i, a) in enumerate(an):
	i += 1
	if a > 0:
		max_value += a
		mf.add_link(i, n + 1, a)
	else:
		mf.add_link(0, i, -a)
	for j in range(2 * i, n + 1, i):
		mf.add_link(i, j, float('inf'))
print(max_value - mf.max_flow(0, n + 1))


from collections import deque

class Dinic:

	def __init__(self, n: int):
		self.INF = float('inf')
		self.n = n
		self.graph = [[] for _ in range(n)]

	def add_edge(self, _from: int, to: int, capacity: int):
		forward = [to, capacity, None]
		forward[2] = backward = [_from, 0, forward]
		self.graph[_from].append(forward)
		self.graph[to].append(backward)

	def bfs(self, s: int, t: int):
		self.level = [-1] * self.n
		q = deque([s])
		self.level[s] = 0
		while q:
			_from = q.popleft()
			for (to, capacity, _) in self.graph[_from]:
				if capacity > 0 and self.level[to] < 0:
					self.level[to] = self.level[_from] + 1
					q.append(to)

	def dfs(self, _from: int, t: int, f: int) -> int:
		if _from == t:
			return f
		for edge in self.itr[_from]:
			(to, capacity, reverse_edge) = edge
			if capacity > 0 and self.level[_from] < self.level[to]:
				d = self.dfs(to, t, min(f, capacity))
				if d > 0:
					edge[1] -= d
					reverse_edge[1] += d
					return d
		return 0

	def max_flow(self, s: int, t: int):
		flow = 0
		while True:
			self.bfs(s, t)
			if self.level[t] < 0:
				break
			self.itr = list(map(iter, self.graph))
			f = self.dfs(s, t, self.INF)
			while f > 0:
				flow += f
				f = self.dfs(s, t, self.INF)
		return flow
n = int(input())
a = list(map(int, input().split()))
dinic = Dinic(n + 2)
s = 0
t = n + 1
_sum = 0
for i in range(0, n):
	if a[i] > 0:
		dinic.add_edge(s, i + 1, 0)
		dinic.add_edge(i + 1, t, a[i])
		_sum += a[i]
	elif a[i] < 0:
		dinic.add_edge(s, i + 1, -a[i])
		dinic.add_edge(i + 1, t, 0)
	else:
		dinic.add_edge(s, i + 1, 0)
		dinic.add_edge(i + 1, t, 0)
for i in range(n):
	num = i + 1
	next_num = 2 * num
	while next_num <= n:
		dinic.add_edge(num, next_num, 10 ** 18)
		next_num += num
print(_sum - dinic.max_flow(s, t))


import sys
INF = 1 << 60
MOD = 10 ** 9 + 7
sys.setrecursionlimit(2147483647)
input = lambda : sys.stdin.readline().rstrip()

class MaxFlow(object):

	def __init__(self, n):
		self.n = n
		self.E = [[] for _ in range(n)]

	def add_edge(self, u, v, cap):
		e = [v, cap, 0]
		rev = [u, 0, e]
		e[-1] = rev
		self.E[u].append(e)
		self.E[v].append(rev)

	def _bfs(self, s, t):
		self._level = level = [-1] * self.n
		level[s] = 0
		queue = [s]
		for v in queue:
			for (nv, cap, _) in self.E[v]:
				if cap and level[nv] == -1:
					level[nv] = level[v] + 1
					if nv == t:
						return True
					queue.append(nv)
		return level[t] != -1

	def _dfs(self, s, t):
		(E, level, it) = (self.E, self._level, self._iter)
		stack = [(s, INF)]
		while stack:
			(v, f) = stack[-1]
			if v == t:
				for (v, _) in stack[:-1]:
					E[v][it[v]][1] -= f
					E[v][it[v]][-1][1] += f
				return f
			while it[v] < len(E[v]):
				(nv, cap, _) = E[v][it[v]]
				if cap and level[v] < level[nv]:
					stack.append((nv, min(f, cap)))
					break
				it[v] += 1
			else:
				stack.pop()
				level[v] = 0
		return 0

	def solve(self, s, t):
		res = 0
		while self._bfs(s, t):
			self._iter = [0] * self.n
			f = 1
			while f:
				f = self._dfs(s, t)
				res += f
		return res

def resolve():
	n = int(input())
	A = list(map(int, input().split()))
	(s, t) = (0, n + 1)
	flow = MaxFlow(n + 2)
	ans = sum((a for a in A if a > 0))
	for u in range(1, n + 1):
		for v in range(2 * u, n + 1, u):
			flow.add_edge(u, v, INF)
	for (v, a) in enumerate(A, 1):
		flow.add_edge(s, v, max(-a, 0))
		flow.add_edge(v, t, max(a, 0))
	ans -= flow.solve(s, t)
	print(ans)
resolve()


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 15
mod = 10 ** 9 + 7

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def divisions(n):
	sq = int(math.sqrt(n) + 1)
	d = collections.defaultdict(int)
	while n % 2 == 0:
		n //= 2
		d[2] += 1
	i = 3
	while n > 1 and sq >= i:
		if n % i == 0:
			n //= i
			d[i] += 1
		else:
			i += 2
	if n > 1:
		d[n] += 1
	r = [1]
	for (k, v) in d.items():
		for c in r[:]:
			for i in range(1, v + 1):
				r.append(c * k ** i)
	return sorted(r)

def main():
	n = I()
	a = LI()
	s = set()
	for i in range(n, 0, -1):
		d = divisions(i)
		ld = len(d)
		for j in range(1, 2 ** ld):
			c = []
			ff = True
			for k in range(ld):
				if j & 1 << k:
					f = True
					for e in c:
						if d[k] % e == 0:
							f = False
							ff = False
							break
					if f:
						c.append(d[k])
				if not ff:
					break
			if ff:
				s.add(tuple(c + [n + 1]))
	b = sorted(list(s), reverse=True)
	for c in b:
		t = 0
		for j in range(1, n + 1):
			f = False
			for e in c:
				if j % e == 0:
					f = True
					break
			if f:
				t += a[j - 1]
		if t < 0:
			for j in range(1, n + 1):
				f = False
				for e in c:
					if j % e == 0:
						f = True
						break
				if f:
					a[j - 1] = 0
	return sum(a)
print(main())


import sys
from collections import deque
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

class EDOMONDS_KARP:

	def __init__(self, N, s, t):
		self.N = N
		self.s = s
		self.t = t
		self.cap = [[0] * N for _ in range(N)]
		self.link = [[] for _ in range(N)]

	def add_edge(self, u, v, c):
		self.cap[u][v] = c
		self.link[u].append(v)
		self.link[v].append(u)

	def max_flow(self):
		N = self.N
		s = self.s
		t = self.t
		f = 0
		flow = [[0] * N for _ in range(N)]
		while True:
			(m, prev) = self.bfs(flow)
			if m == 0:
				break
			f += m
			v = t
			while v != s:
				u = prev[v]
				flow[u][v] += m
				flow[v][u] -= m
				v = u
		return (f, flow)

	def bfs(self, flow):
		N = self.N
		s = self.s
		t = self.t
		cap = self.cap
		link = self.link
		prev = [-1] * N
		prev[s] = -2
		m = [0] * N
		m[s] = float('inf')
		q = deque([s])
		while q:
			u = q.popleft()
			for v in link[u]:
				if cap[u][v] - flow[u][v] > 0 and prev[v] == -1:
					prev[v] = u
					m[v] = min(m[u], cap[u][v] - flow[u][v])
					if v != t:
						q.append(v)
					else:
						return (m[t], prev)
		return (0, prev)

def main():
	INF = float('inf')
	N = int(readline())
	A = list(map(int, readline().split()))
	(S, T) = (0, N + 1)
	EK = EDOMONDS_KARP(N + 2, S, T)
	add = EK.add_edge
	for i in range(1, N + 1):
		a = A[i - 1]
		if a <= 0:
			add(S, i, -a)
		else:
			add(i, T, a)
		for j in range(2, N // i + 1):
			add(i, i * j, INF)
	(f, _) = EK.max_flow()
	print(sum([x for x in A if x > 0]) - f)

def __starting_point():
	main()
__starting_point()


from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque, Counter, defaultdict
from operator import mul
import copy
import heapq
sys.setrecursionlimit(10 ** 6)
INF = 10 ** 18
import bisect
import statistics
mod = 10 ** 9 + 7
from collections import deque

class Dinic:

	def __init__(self, N):
		self.N = N
		self.G = [[] for i in range(N)]

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.G[fr].append(forward)
		self.G[to].append(backward)

	def add_multi_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.G[v1].append(edge1)
		self.G[v2].append(edge2)

	def bfs(self, s, t):
		self.level = level = [None] * self.N
		deq = deque([s])
		level[s] = 0
		G = self.G
		while deq:
			v = deq.popleft()
			lv = level[v] + 1
			for (w, cap, _) in G[v]:
				if cap and level[w] is None:
					level[w] = lv
					deq.append(w)
		return level[t] is not None

	def dfs(self, v, t, f):
		if v == t:
			return f
		level = self.level
		for e in self.it[v]:
			(w, cap, rev) = e
			if cap and level[v] < level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		INF = 10 ** 9 + 7
		G = self.G
		while self.bfs(s, t):
			(*self.it,) = map(iter, self.G)
			f = INF
			while f:
				f = self.dfs(s, t, INF)
				flow += f
		return flow
N = int(input())
a = [0] + list(map(int, input().split()))
dinic = Dinic(N + 2)
for i in range(1, N + 1):
	x = a[i]
	if x >= 0:
		dinic.add_edge(0, i, 0)
		dinic.add_edge(i, N + 1, x)
	else:
		dinic.add_edge(0, i, abs(x))
		dinic.add_edge(i, N + 1, 0)
for i in range(1, N + 1):
	for j in range(2, N // i + 1):
		dinic.add_edge(i, j * i, INF)
print(sum([max(aa, 0) for aa in a]) - dinic.flow(0, N + 1))


from typing import NamedTuple, Optional, List, cast

class MFGraph:

	class Edge(NamedTuple):
		src: int
		dst: int
		cap: int
		flow: int

	class _Edge:

		def __init__(self, dst: int, cap: int) -> None:
			self.dst = dst
			self.cap = cap
			self.rev: Optional[MFGraph._Edge] = None

	def __init__(self, n: int) -> None:
		self._n = n
		self._g: List[List[MFGraph._Edge]] = [[] for _ in range(n)]
		self._edges: List[MFGraph._Edge] = []

	def add_edge(self, src: int, dst: int, cap: int) -> int:
		assert 0 <= src < self._n
		assert 0 <= dst < self._n
		assert 0 <= cap
		m = len(self._edges)
		e = MFGraph._Edge(dst, cap)
		re = MFGraph._Edge(src, 0)
		e.rev = re
		re.rev = e
		self._g[src].append(e)
		self._g[dst].append(re)
		self._edges.append(e)
		return m

	def get_edge(self, i: int) -> Edge:
		assert 0 <= i < len(self._edges)
		e = self._edges[i]
		re = cast(MFGraph._Edge, e.rev)
		return MFGraph.Edge(re.dst, e.dst, e.cap + re.cap, re.cap)

	def edges(self) -> List[Edge]:
		return [self.get_edge(i) for i in range(len(self._edges))]

	def change_edge(self, i: int, new_cap: int, new_flow: int) -> None:
		assert 0 <= i < len(self._edges)
		assert 0 <= new_flow <= new_cap
		e = self._edges[i]
		e.cap = new_cap - new_flow
		assert e.rev is not None
		e.rev.cap = new_flow

	def flow(self, s: int, t: int, flow_limit: Optional[int]=None) -> int:
		assert 0 <= s < self._n
		assert 0 <= t < self._n
		assert s != t
		if flow_limit is None:
			flow_limit = cast(int, sum((e.cap for e in self._g[s])))
		current_edge = [0] * self._n
		level = [0] * self._n

		def fill(arr: List[int], value: int) -> None:
			for i in range(len(arr)):
				arr[i] = value

		def bfs() -> bool:
			fill(level, self._n)
			queue = []
			q_front = 0
			queue.append(s)
			level[s] = 0
			while q_front < len(queue):
				v = queue[q_front]
				q_front += 1
				next_level = level[v] + 1
				for e in self._g[v]:
					if e.cap == 0 or level[e.dst] <= next_level:
						continue
					level[e.dst] = next_level
					if e.dst == t:
						return True
					queue.append(e.dst)
			return False

		def dfs(lim: int) -> int:
			stack = []
			edge_stack: List[MFGraph._Edge] = []
			stack.append(t)
			while stack:
				v = stack[-1]
				if v == s:
					flow = min(lim, min((e.cap for e in edge_stack)))
					for e in edge_stack:
						e.cap -= flow
						assert e.rev is not None
						e.rev.cap += flow
					return flow
				next_level = level[v] - 1
				while current_edge[v] < len(self._g[v]):
					e = self._g[v][current_edge[v]]
					re = cast(MFGraph._Edge, e.rev)
					if level[e.dst] != next_level or re.cap == 0:
						current_edge[v] += 1
						continue
					stack.append(e.dst)
					edge_stack.append(re)
					break
				else:
					stack.pop()
					if edge_stack:
						edge_stack.pop()
					level[v] = self._n
			return 0
		flow = 0
		while flow < flow_limit:
			if not bfs():
				break
			fill(current_edge, 0)
			while flow < flow_limit:
				f = dfs(flow_limit - flow)
				flow += f
				if f == 0:
					break
		return flow

	def min_cut(self, s: int) -> List[bool]:
		visited = [False] * self._n
		stack = [s]
		visited[s] = True
		while stack:
			v = stack.pop()
			for e in self._g[v]:
				if e.cap > 0 and (not visited[e.dst]):
					visited[e.dst] = True
					stack.append(e.dst)
		return visited
import sys
input = sys.stdin.readline
n = int(input())
A = tuple(map(int, input().split()))
G = MFGraph(n + 2)
s = 0
t = n + 1
INF = 10 ** 18
ans = 0
for (i, a) in enumerate(A, 1):
	if a < 0:
		G.add_edge(s, i, -a)
	if a > 0:
		G.add_edge(i, t, a)
		ans += a
	for j in range(2 * i, n + 1, i):
		G.add_edge(i, j, INF)
ans -= G.flow(s, t)
print(ans)


from sys import stdin
from fractions import gcd
from functools import reduce

def lcm(x, y):
	return x * (y // gcd(x, y))

def multiples(t, N):
	return set((i for x in t for i in range(x, N + 1, x)))

def value(a, t):
	return sum((a[i - 1] for i in multiples(t, len(a))))

def remove(a, t):
	for i in multiples(t, len(a)):
		a[i - 1] = 0

def tuples(m, N):
	if m > N:
		return [()]
	ts = tuples(m + 1, N)
	us = [(m,) + t for t in ts if reduce(lcm, t, m) <= N and all((j % m != 0 for j in t))]
	ts.extend(us)
	return ts

def solve(a):
	N = len(a)
	for t in tuples(1, N):
		if value(a, t) < 0:
			remove(a, t)
	return sum(a)
N = int(stdin.readline())
a = [int(w) for w in stdin.readline().split()]
if len(a) != N:
	raise
print(solve(a))


from collections import deque
INF = 10 ** 30

class Dinic:

	def __init__(self, n):
		self.n = n
		self.g = [[] for i in range(n)]

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.g[fr].append(forward)
		self.g[to].append(backward)

	def add_bidirectional_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.g[v1].append(edge1)
		self.g[v2].append(edge2)

	def bfs(self, s, t):
		self.level = level = [None] * self.n
		deq = deque([s])
		level[s] = 0
		g = self.g
		while deq:
			v = deq.popleft()
			lv = level[v] + 1
			for (w, cap, _) in g[v]:
				if cap and level[w] is None:
					level[w] = lv
					deq.append(w)
		return level[t] is not None

	def dfs(self, v, t, f):
		if v == t:
			return f
		level = self.level
		for e in self.it[v]:
			(w, cap, rev) = e
			if cap and level[v] < level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		g = self.g
		while self.bfs(s, t):
			(*self.it,) = map(iter, self.g)
			f = INF
			while f:
				f = self.dfs(s, t, INF)
				flow += f
		return flow
n = int(input())
a = [-1] + list(map(int, input().split()))
d = Dinic(n + 2)
(s, t) = (0, n + 1)
for i in range(1, n + 1):
	if a[i] > 0:
		d.add_edge(i, t, a[i])
	elif a[i] < 0:
		d.add_edge(s, i, -a[i])
	for j in range(2 * i, n + 1, i):
		d.add_edge(i, j, INF)
res = d.flow(s, t)
print(sum([x for x in a if x > 0]) - res)


class FK:

	def __init__(self, n):
		self.table = [[0] * n for i in range(n)]
		self.n = n

	def add(self, x, y, f):
		self.table[x][y] = f

	def ford(self, s, t, f):
		self.visit[s] = True
		if s == t:
			return f
		for i in range(self.n):
			if not self.visit[i] and self.table[s][i] > 0:
				df = self.ford(i, t, min(f, self.table[s][i]))
				if df > 0:
					self.table[s][i] -= df
					self.table[i][s] += df
					return df
		return 0

	def flow(self, s, t):
		ans = 0
		inf = 10 ** 20
		while True:
			self.visit = [False] * self.n
			df = self.ford(s, t, inf)
			if df == 0:
				break
			ans += df
		return ans
N = int(input())
P = [int(i) for i in input().split()]
inf = 10 ** 20
maxflow = FK(N + 2)
for i in range(1, N + 1):
	if P[i - 1] > 0:
		maxflow.add(i, N + 1, P[i - 1])
	else:
		maxflow.add(0, i, -P[i - 1])
	for j in range(2 * i, N + 1, i):
		maxflow.add(i, j, inf)
ans = maxflow.flow(0, N + 1)
num = sum([p for p in P if p > 0])
print(num - ans)


from collections import deque

class Dinic:

	def __init__(self, N, inf):
		self.N = N
		self.inf = inf
		self.G = [[] for _ in range(N)]
		self.level = [0] * N

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.G[fr].append(forward)
		self.G[to].append(backward)

	def add_multi_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.G[v1].append(edge1)
		self.G[v2].append(edge2)

	def bfs(self, s):
		self.level = [-1] * self.N
		deq = deque([s])
		self.level[s] = 0
		while deq:
			v = deq.pop()
			lv = self.level[v] + 1
			for (w, cap, _) in self.G[v]:
				if cap > 0 and self.level[w] == -1:
					self.level[w] = lv
					deq.appendleft(w)

	def dfs(self, v, t, f):
		if v == t:
			return f
		for e in self.iter[v]:
			(w, cap, rev) = e
			if cap > 0 and self.level[v] < self.level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d > 0:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		while True:
			self.bfs(s)
			if self.level[t] == -1:
				return flow
			(*self.iter,) = list(map(iter, self.G))
			f = self.inf
			while f > 0:
				f = self.dfs(s, t, self.inf)
				flow += f
import sys
sys.setrecursionlimit(10 ** 7)

def I():
	return int(sys.stdin.readline().rstrip())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))
N = I()
A = [0] + LI()
ans = sum((A[i] for i in range(1, N + 1) if A[i] > 0))
inf = 10 ** 18
Di = Dinic(N + 2, inf)
(s, t) = (0, N + 1)
for i in range(1, N + 1):
	Di.add_edge(s, i, max(0, -A[i]))
	Di.add_edge(i, t, max(0, A[i]))
for i in range(1, N // 2 + 1):
	for j in range(2 * i, N + 1, i):
		Di.add_edge(i, j, inf)
print(ans - Di.flow(s, t))


def main():
	import sys
	input = sys.stdin.readline
	from collections import deque

	class Dinic:

		def __init__(self, N):
			self.N = N
			self.G = [[] for i in range(N)]

		def add_edge(self, fr, to, cap):
			forward = [to, cap, None]
			forward[2] = backward = [fr, 0, forward]
			self.G[fr].append(forward)
			self.G[to].append(backward)

		def add_multi_edge(self, v1, v2, cap1, cap2):
			edge1 = [v2, cap1, None]
			edge1[2] = edge2 = [v1, cap2, edge1]
			self.G[v1].append(edge1)
			self.G[v2].append(edge2)

		def bfs(self, s, t):
			self.level = level = [None] * self.N
			deq = deque([s])
			level[s] = 0
			G = self.G
			while deq:
				v = deq.popleft()
				lv = level[v] + 1
				for (w, cap, _) in G[v]:
					if cap and level[w] is None:
						level[w] = lv
						deq.append(w)
			return level[t] is not None

		def dfs(self, v, t, f):
			if v == t:
				return f
			level = self.level
			for e in self.it[v]:
				(w, cap, rev) = e
				if cap and level[v] < level[w]:
					d = self.dfs(w, t, min(f, cap))
					if d:
						e[1] -= d
						rev[1] += d
						return d
			return 0

		def flow(self, s, t):
			flow = 0
			INF = 10 ** 9 + 7
			G = self.G
			while self.bfs(s, t):
				(*self.it,) = map(iter, self.G)
				f = INF
				while f:
					f = self.dfs(s, t, INF)
					flow += f
			return flow
	inf = 1 << 40
	N = int(input())
	A = list(map(int, input().split()))
	dinic = Dinic(N + 2)
	ans = 0
	for (i, a) in enumerate(A):
		if a > 0:
			ans += a
			dinic.add_edge(i + 1, N + 1, a)
		else:
			dinic.add_edge(0, i + 1, -a)
	for i in range(1, N + 1):
		for k in range(1, N + 1):
			if i * k > N:
				break
			dinic.add_edge(i, i * k, inf)
	print(ans - dinic.flow(0, N + 1))
main()


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return list(map(int, input().split()))

def LIST():
	return list(map(int, input().split()))

def ZIP(n):
	return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 10
mod = 10 ** 9 + 7

class Dinic:

	def __init__(self, v, inf=10 ** 10):
		self.v = v
		self.inf = inf
		self.G = [[] for _ in range(v)]
		self.level = [-1] * v
		self.ite = [0] * v

	def add_edge(self, fr, to, cap):
		self.G[fr].append([to, cap, len(self.G[to])])
		self.G[to].append([fr, 0, len(self.G[fr]) - 1])

	def bfs(self, s):
		self.level = [-1] * self.v
		self.level[s] = 0
		Q = deque()
		Q.append(s)
		while Q:
			v = Q.popleft()
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if e[1] > 0 and self.level[e[0]] < 0:
					self.level[e[0]] = self.level[v] + 1
					Q.append(e[0])

	def dfs(self, v, t, f):
		if v == t:
			return f
		for i in range(self.ite[v], len(self.G[v])):
			self.ite[v] = i
			e = self.G[v][i]
			if e[1] > 0 and self.level[v] < self.level[e[0]]:
				d = self.dfs(e[0], t, min(f, e[1]))
				if d > 0:
					e[1] -= d
					self.G[e[0]][e[2]][1] += d
					return d
		return 0

	def max_flow(self, s, t):
		flow = 0
		while True:
			self.bfs(s)
			if self.level[t] < 0:
				return flow
			self.ite = [0] * self.v
			f = self.dfs(s, t, self.inf)
			while f > 0:
				flow += f
				f = self.dfs(s, t, self.inf)
N = INT()
a = LIST()
D = Dinic(N + 2)
s = 0
t = N + 1
rw = 0
for (i, x) in enumerate(a):
	if x <= 0:
		D.add_edge(s, i + 1, -x)
	elif x > 0:
		D.add_edge(i + 1, t, x)
		rw += x
	for j in range(2 * (i + 1), N + 1, i + 1):
		D.add_edge(i + 1, j, INF)
print(rw - D.max_flow(s, t))


import sys
INF = 1 << 60
MOD = 10 ** 9 + 7
sys.setrecursionlimit(2147483647)
input = lambda : sys.stdin.readline().rstrip()
import networkx as nx

def resolve():
	n = int(input())
	A = list(map(int, input().split()))
	total = sum((a for a in A if a > 0))
	G = nx.DiGraph()
	G.add_nodes_from(range(1, n + 1))
	G.add_nodes_from(['source', 'termination'])
	for (i, a) in enumerate(A, 1):
		if a >= 0:
			G.add_edge('source', i, capacity=0)
			G.add_edge(i, 'termination', capacity=a)
		else:
			G.add_edge('source', i, capacity=-a)
			G.add_edge(i, 'termination', capacity=0)
	for i in range(1, n + 1):
		for j in range(2 * i, n + 1, i):
			G.add_edge(i, j, capacity=INF)
	flow = nx.algorithms.flow.maximum_flow_value(G, 'source', 'termination')
	print(total - flow)
resolve()


import networkx as nx
from networkx.algorithms.flow import dinitz
n = int(input())
A = list(map(int, input().split()))
G = nx.DiGraph()
source = 'source'
sink = 'sink'
for i in range(1, n + 1):
	if A[i - 1] <= 0:
		G.add_edge(source, i, capacity=-A[i - 1])
	else:
		G.add_edge(i, sink, capacity=A[i - 1])
for i in range(1, n // 2 + 1):
	for j in range(2 * i, n + 1, i):
		G.add_edge(i, j)
try:
	R = dinitz(G, source, sink)
	res = sum((a for a in A if a > 0))
	print(res - R.graph['flow_value'])
except nx.NetworkXError:
	print(0)


from collections import deque
N = int(input())
P = [int(i) for i in input().split()]
inf = 10 ** 20
table = [[0] * (N + 2) for i in range(N + 2)]
for i in range(1, N + 1):
	if P[i - 1] > 0:
		table[i][N + 1] = P[i - 1]
	else:
		table[0][i] = -P[i - 1]
	for j in range(2 * i, N + 1, i):
		table[i][j] = inf

def bfs(x):
	visit[x] = 0
	h = deque()
	h.append(x)
	while h:
		y = h.popleft()
		for i in range(N + 2):
			if visit[i] == -1 and table[y][i] > 0:
				visit[i] = visit[y] + 1
				h.append(i)
	return 0

def dinic(s, t, f):
	if s == t:
		return f
	for i in range(N + 2):
		if visit[i] > visit[s] and table[s][i] > 0:
			df = dinic(i, t, min(f, table[s][i]))
			if df > 0:
				table[s][i] -= df
				table[i][s] += df
				return df
	return 0
ans = 0
while True:
	visit = [-1] * (N + 2)
	bfs(0)
	if visit[N + 1] == -1:
		break
	while True:
		df = dinic(0, N + 1, inf)
		if df == 0:
			break
		ans += df
num = sum([p for p in P if p > 0])
print(num - ans)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
import time, random
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
mod2 = 998244353
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

class Flow:

	def __init__(self, e, N):
		self.E = e
		self.N = N

	def max_flow(self, s, t):
		r = 0
		e = self.E

		def f(c, cap):
			v = self.v
			v[c] = 1
			if c == t:
				return cap
			for i in range(self.N):
				if v[i] or e[c][i] <= 0:
					continue
				cp = min(cap, e[c][i])
				k = f(i, cp)
				if k > 0:
					e[c][i] -= k
					e[i][c] += k
					return k
			return 0
		while True:
			self.v = [None] * self.N
			fs = f(s, inf)
			if fs == 0:
				break
			r += fs
		return r

def main():
	n = I()
	a = LI()
	s = n
	t = n + 1
	e = [[0] * (n + 2) for _ in range(n + 2)]
	for i in range(n):
		c = a[i]
		if c < 0:
			e[s][i] = -c
			ii = i + 1
			for j in range(ii * 2, n + 1, ii):
				e[i][j - 1] = inf
		else:
			e[i][t] = c
	fl = Flow(e, n + 2)
	r = fl.max_flow(s, t)
	return sum(map(lambda x: max(0, x), a)) - r
print(main())


from collections import deque
import sys
sys.setrecursionlimit(200000)
n = int(input())
houseki = list(map(int, input().split()))
g = [[] for i in range(n + 2)]
INF = float('inf')
MAX = 0
for i in range(n):
	if houseki[i] <= 0:
		g[0].append([i + 1, -houseki[i], len(g[i + 1])])
		g[i + 1].append([0, 0, len(g[0]) - 1])
	else:
		g[n + 1].append([i + 1, 0, len(g[i + 1])])
		g[i + 1].append([n + 1, houseki[i], len(g[n + 1]) - 1])
		MAX += houseki[i]
	j = (i + 1) * 2
	while j <= n:
		g[i + 1].append([j, INF, len(g[j])])
		g[j].append([i + 1, 0, len(g[i + 1]) - 1])
		j += i + 1

def bfs(s, t):
	nonlocal level
	que = deque([s])
	level[s] = 0
	while que:
		v = que.popleft()
		lv = level[v] + 1
		for (y, cap, rev) in g[v]:
			if cap and level[y] is None:
				level[y] = lv
				que.append(y)
	return level[t] if level[t] else 0

def dfs(x, t, f):
	if x == t:
		return f
	for j in range(it[x], len(g[x])):
		it[x] = j
		(y, cap, rev) = g[x][j]
		if cap and level[x] < level[y]:
			d = dfs(y, t, min(f, cap))
			if d:
				g[x][j][1] -= d
				g[y][rev][1] += d
				return d
	return 0
flow = 0
f = INF = float('inf')
level = [None] * (n + 2)
while bfs(0, n + 1):
	it = [0] * (n + 2)
	f = INF
	while f:
		f = dfs(0, n + 1, INF)
		flow += f
	level = [None] * (n + 2)
print(MAX - flow)