import sequtils,algorithm # import ,math,tables # import sets,intsets,queues,heapqueue,bitops,strutils # import strutils,strformat,sugar,macros # template stopwatch(body) = (let t1 = cpuTime();body;echo "TIME:",(cpuTime() - t1) * 1000,"ms") template times*(n:int,body) = (for _ in 0.." .} proc scan(): int = while true: let k = getchar_unlocked() if k < '0': return result = 10 * result + k.ord - '0'.ord let n = scan() let M = newSeqWith(n,scan()).sorted(cmp) const INF = 1e10.int var ans = INF var dp = newSeqWith[int](^n + 1,INF) # proc solve(s,total,buyTotal:int) = # if s == ^n - 1: # ans .min= total # return # if dp[s] <= total : return # dp[s] = total # for x in 0.. 0 : continue # solve(s or ^x,total + (M[x] - (buyTotal mod 1000)).max(0),buyTotal+M[x]) # solve(0,0,0) proc solve() = for x in 0..<(^n - 1): var total = 0 for i in 0.. 0 : total += M[i] total = total mod 1000 for i in 0.. 0 : continue dp[x or ^i] .min= dp[x] + 0.max(M[i] - total) dp[0] = 0 solve() echo dp[^n-1]