Problem:
 Score : 700 points    Problem Statement 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 1 6
1 2 -6 4 5 3      Sample Output 1 12  It is optimal to smash Gem 3 and 6 .       Sample Input 2 6
100 -100 -100 -100 100 -100      Sample Output 2 200       Sample Input 3 5
-1 -2 -3 -4 -5      Sample Output 3 0  It is optimal to smash all the gems.       Sample Input 4 2
-1000 100000      Sample Output 4 99000

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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())

Solution (Python):
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()

Solution (Python):
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


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())
a = list( map(int, input().split()))

score = 0
INF = float('inf')
graph = Dinic(n+2)

for i in range(n):
    if a[i]>0:
        graph.add_edge(i+1,n+1,a[i])
        score += a[i]
    elif a[i]<0:
        graph.add_edge(0,i+1,-a[i])

for i in range(1,n//2+1):
    for j in range(2*i,n+1,i):
        graph.add_edge(i,j,INF)

print(score-graph.flow(0,n+1))

Solution (Python):

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


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())
a = list( map(int, input().split()))

score = 0
INF = float('inf')
graph = Dinic(n+2)

for i in range(n):
    if a[i]>0:
        graph.add_edge(i+1,n+1,a[i])
        score += a[i]
    elif a[i]<0:
        graph.add_edge(0,i+1,-a[i])

for i in range(1,n//2+1):
    for j in range(2*i,n+1,i):
        graph.add_edge(i,j,INF)

print(score-graph.flow(0,n+1))

Solution (Python):

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


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())
a = list( map(int, input().split()))

score = 0
INF = float('inf')
graph = Dinic(n+2)

for i in range(n):
    if a[i]>0:
        graph.add_edge(i+1,n+1,a[i])
        score += a[i]
    elif a[i]<0:
        graph.add_edge(0,i+1,-a[i])

for i in range(1,n//2+1):
    for j in range(2*i,n+1,i):
        graph.add_edge(i,j,INF)

print(score-graph.flow(0,n+1))

Solution (Python):

"""
https://atcoder.jp/contests/arc085/tasks/arc085_c

"""

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)

Solution (Python):
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())

Solution (Python):
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))

Solution (Python):
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 map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return 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))

Solution (Python):

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

jew=Dinic(N+2)
ans=0
for i in range(N):
    if a[i]>=0:
        ans+=a[i]
        jew.add_edge(0,i+1,a[i])
    else:
        jew.add_edge(i+1,N+1,-a[i])

inf=10**15
for i in range(1,N+1):
    for j in range(1,N//i+1):
        jew.add_edge(i*j,i,inf)

f=jew.flow(0,N+1)
print(ans-f)

Solution (Python):
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)

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



class FordFulkerson:
  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 dfs(self, v, t, f):
    if v == t:
      return f
    used = self.used
    used[v] = 1
    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
    N = self.N 
    while f:
      self.used = [0]*N
      f = self.dfs(s, t, INF)
      flow += f
    return flow

asum_pos=0  

ff = FordFulkerson(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)

Solution (Python):
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()
A = LI()
score = 0
s = 0
t = n + 1
dinic = Dinic(s, t)
for i in range(1, n + 1):
    if A[i - 1] > 0:
        score += 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)
    ret = i
    while ret + i <= n:
        ret += i
        dinic.add_edge(i, ret, INF)


print(score - dinic.max_flow())

Solution (Python):
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):
        """
        G[fr] = [to, cap, rev]
        """
        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())