CodeEff/ECCO huggingface dataset:
# Original solution
from heapq import heapify,heappush, heappop

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

q=A[:N]
heapify(q)
q_sum=sum(q)

B=[ float("-inf") for i in range(3*N)]
B[N-1]=q_sum

for i in range(N,2*N):
	x=A[i]
	if x>q[0]:
		tmp=heappop(q)
		q_sum-=tmp
		q_sum+=x
		heappush(q,x)
	B[i]=q_sum

q=[x*-1 for x in A[2*N:]]
heapify(q)

q_sum=sum(q)*-1
B[2*N-1]-=q_sum

for i in range(2*N-1,N-1,-1):
	x=A[i]*-1
	if q[0]<x:
		tmp=heappop(q)
		q_sum-=tmp*-1
		q_sum+=x*-1
		heappush(q,x)
	B[i-1]-=q_sum

print(max(B))

# Optimized solution
from heapq import heapify,heappush, heappop

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

hq1=A[:N]
heapify(hq1)
sum1=sum(hq1)


T1=[]
T1.append(sum1)

for i in range(N, 2*N):
	x=A[i]
	if hq1[0]<x:
		u=heappop(hq1)
		heappush(hq1,x)
		sum1+=(x-u)
	T1.append(sum1)


hq2=[x*-1 for x in A[2*N:]]
sum2=-1*sum(hq2)
heapify(hq2)



T2=[]
T2.append(sum2)

for i in range(2*N-1,N-1,-1):
	x=A[i]
	if x*-1 > hq2[0]<x:
			u=heappop(hq2)
			heappush(hq2,x*-1)
			sum2+=u+x

	T2.append(sum2)


T2.reverse()


ans=float("-inf")
for x, y in zip(T1, T2):
	ans=max(ans , x-y)
print(ans)
# Original solution
from heapq import heappush, heappop
n=int(eval(input()))
a=list(map(int,input().split()))
l=[]
for v in a[:n]:
  heappush(l,v)
suml=[sum(a[:n])]
for i in range(n):
  suml.append(suml[i]+a[n+i])
  heappush(l,a[n+i])
  suml[i+1]-=heappop(l)
r=[]
for v in a[2*n:]:
  heappush(r,(10**10-v,v))
sumr=[sum(a[2*n:])]
for i in range(n):
  sumr.append(sumr[i]+a[2*n-i-1])
  heappush(r,(10**10-a[2*n-i-1],a[2*n-i-1]))
  _,t=heappop(r)
  sumr[i+1]-=t
ans=-10**20
for i in range(n+1):
  ans=max(ans,suml[i]-sumr[n-i])
print(ans)

# Optimized solution
def f(a):
	q=a[:n];s=sum(q);heapify(q)
	for e in a[n:n-~n]:yield s;s+=e-heappushpop(q,e)
from heapq import*;n,*a=list(map(int,open(0).read().split()));print((max(list(map(sum,list(zip(f(a),list(f([-e for e in a[::-1]]))[::-1])))))))
# Original solution
import heapq

def solve():
  n = int(input())
  ar = input().split(' ')
  iar = [int(s) for s in ar]
  
  early = iar[:n]
  mid = iar[n:-n]
  late = iar[-n:]

  heapq.heapify(early)
  tmpsum = sum(early)
  esums = [tmpsum]
  for i in range(n):
    heapq.heappush(early, mid[i])
    emin = heapq.heappop(early)
    tmpsum += (mid[i] - emin)
    esums.append(tmpsum)
  #print esums
 
  lateinv = [-x for x in late]
  heapq.heapify(lateinv)
  tmpsum = sum(lateinv)
  lsums = [tmpsum]
  for i in range(1,n+1):
    heapq.heappush(lateinv, -mid[-i])
    lmax = heapq.heappop(lateinv)
    tmpsum += (-mid[-i] - lmax)
    lsums.append(tmpsum)
  #print lsums
  
  best = float("-inf")
  for i in range(n+1):
    score = esums[i] + lsums[n-i]
    #print 'i=',i,',n-i=',n-i,',esums[i]=',esums[i],',lsums[n-i]=',lsums[n-i],'score=',score
    if(best < score) : best = score
  return best

if __name__ == '__main__' :
  print(solve())

# Optimized solution
import heapq
N = int(eval(input()))
src = list(map(int,input().split()))

lsum = sum(src[:N])
lmem = [lsum]
lq = src[:N][:]
heapq.heapify(lq)
for a in src[N:2*N]:
    if a <= lq[0]:
        lmem.append(lmem[-1])
    else:
        lsum += a - heapq.heappop(lq)
        heapq.heappush(lq, a)
        lmem.append(lsum)

rq = [-a for a in src[-N:]]
rsum = sum(rq)
rmem = [rsum]
heapq.heapify(rq)
for a in reversed(src[N:2*N]):
    if -a <= rq[0]:
        rmem.append(rmem[-1])
    else:
        rsum += -a - heapq.heappop(rq)
        heapq.heappush(rq, -a)
        rmem.append(rsum)

ans = -float('inf')
for l,r in zip(lmem, rmem[::-1]):
    ans = max(ans, l+r)
print(ans)
# Original solution
import heapq

N = int(eval(input()))
A = list(map(int, input().split()))
 
L = A[:N]
heapq.heapify(L) 

sum_L = [0] * (N+1)
sum_L[0] = sum(L)

for i in range(N):
    min_L = heapq.heappushpop(L, A[N+i])
    sum_L[i+1] = sum_L[i] + A[N+i] - min_L
    #print(L, i, A[N+i], min_L, sum_L)

R = A[N*2:]
rev_R = list([x*(-1) for x in R])
heapq.heapify(rev_R) 

sum_R = [0] * (N+1)
sum_R[N] = sum(R)

for i in range(N-1, -1, -1):
    max_R = heapq.heappushpop( rev_R, A[N+i]*(-1) ) * (-1)
    sum_R[i] = sum_R[i+1] + A[N+i] - max_R
    # print(rev_R, i, A[N+i], max_R, sum_R)

ans = -10**14

for i in range(N+1):
    ans = max(ans, sum_L[i] - sum_R[i])

print(ans)

# Optimized solution
import heapq

N = int(eval(input()))
A = list(map(int, input().split()))
 
L = A[:N]
heapq.heapify(L) 

sum_L = [0] * (N+1)
sum_L[0] = sum(L)

for i in range(N):
    min_L = heapq.heappushpop(L, A[N+i])
    sum_L[i+1] = sum_L[i] + A[N+i] - min_L
    #print(L, i, A[N+i], min_L, sum_L)

R = A[N*2:]
rev_R = list([-x for x in R])
heapq.heapify(rev_R) 

sum_R = [0] * (N+1)
sum_R[N] = sum(R)

for i in range(N-1, -1, -1):
    max_R = -heapq.heappushpop(rev_R, -A[N+i])
    sum_R[i] = sum_R[i+1] + A[N+i] - max_R
    #print(rev_R, i, A[N+i], max_R, sum_R)

ans = -10**14

for i in range(N+1):
    ans = max(ans, sum_L[i] - sum_R[i])

print(ans)
# Original solution
import heapq
n=int(eval(input()))
A=[int(i) for i in input().split()]
AL=A[:n]
AR=[]
for i in range(2*n,3*n):
  AR.append(-A[i])
ALS,ARS=[0]*(n+1),[0]*(n+1)
ALS[0],ARS[0]=sum(AL),-sum(AR)
heapq.heapify(AL)
heapq.heapify(AR)
for i in range(n):
  heapq.heappushpop(AL,A[n+i])
  ALS[i+1]+=sum(AL)
  heapq.heappushpop(AR,-A[2*n-i-1])
  ARS[i+1]+=-sum(AR)
ARS=ARS[::-1]
ans=-float("inf")
for i in range(n+1):
  ans=max(ans,ALS[i]-ARS[i])
print(ans)

# Optimized solution
import heapq
n=int(eval(input()))
A=[int(i) for i in input().split()]
AL=A[:n]
AR=[0]*n
for i in range(2*n,3*n):
  AR[i-2*n]-=A[i]
ALS,ARS=[0]*(n+1),[0]*(n+1)
ALS[0],ARS[0]=sum(AL),sum(AR)
heapq.heapify(AL)
heapq.heapify(AR)
for i in range(n):
  l,r=A[n+i],-A[2*n-i-1]
  heapq.heappush(AL,l)
  ALS[i+1]=ALS[i]+l-heapq.heappop(AL)
  heapq.heappush(AR,r)
  ARS[i+1]=ARS[i]+r-heapq.heappop(AR)
ans=-float("inf")
for i in range(n+1):
  ans=max(ans,ALS[i]+ARS[n-i])
print(ans)
# Original solution
from heapq import heappop, heappush

inf = float('inf')

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

# sum_max[k] : [0,k)のうちN個までの総和の最大値
# sum_min[k] : (3N-1-k,3N-1]のうちN個までの総和の最小値
sum_max = [0]*(3*N+1)
sum_min = [0]*(3*N+1)

def init_max():
    res = 0
    hq = []
    for i, a in enumerate(A):
        if len(hq) < N:
            heappush(hq,a)
            res += a
        else:
            if hq[0] < a:
                res -= heappop(hq)
                heappush(hq,a)
                res += a
        sum_max[i+1] = res

def init_min():
    res = 0
    hq = []
    for i, a in enumerate(A[::-1]):
        if len(hq) < N:
            heappush(hq,-a)
            res += a
        else:
            if -hq[0] > a:
                res -= -heappop(hq) 
                heappush(hq,-a)
                res += a
        sum_min[i+1] = res

init_max()
init_min()

ans = -inf

for k in range(N,2*N+1):
    res = sum_max[k] - sum_min[3*N-k]
    ans = max(ans, res)

print(ans)

# Optimized solution
from heapq import heappop, heappush
inf = float('inf')

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

l = []
res = 0
for i in range(N):
    heappush(l, A[i])
    res += A[i]
ls = []
ls.append(res)

for i in range(N, 2*N):
    heappush(l, A[i])
    res += A[i]
    res -= heappop(l)
    ls.append(res)

A.reverse()

s = []
res = 0
for i in range(N):
    heappush(s, -A[i])
    res += A[i]
ss = []
ss.append(res)

for i in range(N, 2*N):
    heappush(s, -A[i])
    res += A[i]
    res -= -heappop(s)
    ss.append(res)

ss.reverse()

ans = -inf

for i in range(N+1):
    score = ls[i] - ss[i]
    ans = max(ans, score)

print(ans)
# Original solution
INF = 10 ** 12

N = int(eval(input()))
X = [0] * N
Y = [0] * N
P = [0] * N
for i in range(N):
    X[i], Y[i], P[i] = list(map(int,input().split()))

score_X = []

for i in range(2 ** N):
    x = []
    I = i
    for j in range(N):
        i = I
        score = abs(X[j]) * P[j]
        for k in range(N):
            if i & 1:
                score = min(score, abs(X[j] - X[k]) * P[j])
            i >>= 1
        x.append(score)
    score_X.append(x)

score_Y = []

for i in range(2 ** N):
    y = []
    I = i
    for j in range(N):
        i = I
        score = abs(Y[j]) * P[j]
        for k in range(N):
            if i & 1:
                score = min(score, abs(Y[j] - Y[k]) * P[j])
            i >>= 1
        y.append(score)
    score_Y.append(y)

ans = [INF] * (N + 1)

for i in range(2 ** N):
    cnt = 0
    for j in range(N):
        if (i >> j) & 1:
            cnt += 1
    for j in range(i, -1, -1):
        j &= i
        score = 0
        for k in range(N):
            if not (i >> k) & 1:
                score += min(score_X[j][k], score_Y[i - j][k])
        ans[cnt] = min(ans[cnt], score)
    

for i in range(N + 1):
    print((ans[i]))

# Optimized solution
INF = 10 ** 12

N = int(eval(input()))
X = [0] * N
Y = [0] * N
P = [0] * N
for i in range(N):
    X[i], Y[i], P[i] = list(map(int,input().split()))

score_X = []

for i in range(2 ** N):
    x = []
    I = i
    for j in range(N):
        i = I
        score = abs(X[j]) * P[j]
        for k in range(N):
            if i & 1:
                score = min(score, abs(X[j] - X[k]) * P[j])
            i >>= 1
        x.append(score)
    score_X.append(x)

score_Y = []

for i in range(2 ** N):
    y = []
    I = i
    for j in range(N):
        i = I
        score = abs(Y[j]) * P[j]
        for k in range(N):
            if i & 1:
                score = min(score, abs(Y[j] - Y[k]) * P[j])
            i >>= 1
        y.append(score)
    score_Y.append(y)

ans = [INF] * (N + 1)

for i in range(2 ** N):
    cnt = 0
    for j in range(N):
        if (i >> j) & 1:
            cnt += 1
    
    j = i
    
    while True:
        score = 0
        for k in range(N):
            if not (i >> k) & 1:
                score += min(score_X[j][k], score_Y[i - j][k])
        ans[cnt] = min(ans[cnt], score)
        if j == 0:
            break
        j = (j - 1) & i

for i in range(N + 1):
    print((ans[i]))
# Original solution
N = int(eval(input()))
X = []; Y = []; P = []
INF = float("inf")
for i in range(N):
  x,y,p = list(map(int,input().split()))
  X.append(x);Y.append(y);P.append(p)
ans = [INF for _ in range(N+1)] #0本置いた時からN本置いた時までN+1個
def calc(A):
  n = len(A) #Aにはいくつ入っているか。つまり、xoryで選ばれたものはいくつあるか。
  A.sort()
  res = [INF for _ in range(n+1)] #道が0本からn本
  for s in range(1<<n): #選ばれたものを全探索
    p = [] #最初の大通り
    for i in range(n):
      if (s>>i)&1 == 1: #bitが立っている位置は道があるので追加
        p.append(A[i][0])
    #p.sort()
    now = 0 #現在の移動距離
    pi = 0 #i個目の町の位置よりも小さい位置
    for i in range(n): #i個目の町に注目
      #m = INF
      x = A[i][0] #xoryとして選ばれた町のi番目の位置。
      while pi+1 < len(p) and p[pi+1] < x:
        pi += 1
      m = abs(x)
      if pi < len(p):
        m = min(m,abs(x-p[pi]))
      if pi+1 < len(p):
        m = min(m,abs(x-p[pi+1]))
      #for j in range(len(p)): #すべての道に対して愚直に最短距離を求める。
      #  m = min(m,abs(p[j]-A[i][0]))
      now += m*A[i][1] #最短距離×人数
    b = len(p) #道を何本追加したか。1を引くのは最初の大通り。
    res[b] = min(res[b],now)
  return res
    

for s in range(1<<N): #x軸にするかをbitで全探索
  AX = [];AY = [] #Aは選ばれた村を追加していく。2**N回これは更新される。
  for i in range(N):
    if (s>>i)&1 == 1: #x軸で見る
      AX.append((X[i],P[i]))
    else:
      AY.append((Y[i],P[i]))
    
  dx = calc(AX)
  dy = calc(AY)
  for i in range(len(dx)):
    for j in range(len(dy)):
      ans[i+j] = min(ans[i+j],dx[i]+dy[j])
for t in ans:
  print(t)

# Optimized solution
N = int(eval(input()))
X = []; Y = []; P = []
INF = float("inf")
for i in range(N):
  x,y,p = list(map(int,input().split()))
  X.append(x);Y.append(y);P.append(p)
ans = [INF for _ in range(N+1)] #0本置いた時からN本置いた時までN+1個

def calc(A):
  n = len(A) #Aにはいくつ入っているか。つまり、xoryで選ばれたものはいくつあるか。
  A.sort()
  dp = [[INF]*(n+1) for _ in range(n+1)] #i個目までカバーしてj個目まで道を置いた。
  dp[0][0] = 0
  for l in range(n):
    for r in range(l+1,n+1):
      now = INF
      for k in range(l,r):
        s = 0
        for i in range(l,r):
          s += abs(A[i][0]-A[k][0])*A[i][1]
        now = min(now,s)
      for j in range(n):
        dp[r][j+1] = min(dp[r][j+1], dp[l][j]+now)
      now = 0
      for i in range(l,r):
        now += abs(A[i][0])*A[i][1]
      for j in range(n+1):
        dp[r][j] = min(dp[r][j], dp[l][j]+now)

  
  res = [INF for _ in range(n+1)] #道が0本からn本
  for j in range(n+1):
    res[j] = dp[n][j]

  return res
    

for s in range(1<<N): #x軸にするかをbitで全探索
  AX = [];AY = [] #Aは選ばれた村を追加していく。2**N回これは更新される。
  for i in range(N):
    if (s>>i)&1 == 1: #x軸で見る
      AX.append((X[i],P[i]))
    else:
      AY.append((Y[i],P[i]))
    
  dx = calc(AX)
  dy = calc(AY)
  for i in range(len(dx)):
    for j in range(len(dy)):
      ans[i+j] = min(ans[i+j],dx[i]+dy[j])
for t in ans:
  print(t)
# Original solution
# writer解(c++)を写経した．answerのfor文のところ何やってるかさっぱりわかりませんが…
# https://atcoder.jp/contests/m-solutions2020/submissions/15122924
import sys
input = sys.stdin.readline
INF = 10**13


def main():
    N = int(eval(input()))
    T = [[int(i) for i in input().split()] for j in range(N)]
    X_dist = [[0]*N for _ in range(1 << N)]
    Y_dist = [[0]*N for _ in range(1 << N)]

    # bitという道路群を建設したときの，各集落の評価距離
    # bit 001001 とかの1が立っている集落に道を作る
    for bit in range(1 << N):
        cur_x = [0]
        cur_y = [0]
        for i in range(N):
            if bit & (1 << i):
                cur_x.append(T[i][0])
                cur_y.append(T[i][1])
        for i in range(N):
            X_dist[bit][i] = T[i][2]*min(abs(cx - T[i][0]) for cx in cur_x)
            Y_dist[bit][i] = T[i][2]*min(abs(cy - T[i][1]) for cy in cur_y)

    # これはなに？
    answer = [INF] * (N+1)
    for i in range(1 << N):
        cnt = 0
        for j in range(N):
            if (i >> j) & 1:
                cnt += 1
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(N):
                if not((i >> k) & 1):
                    cost += min(X_dist[j][k], Y_dist[i - j][k])
            answer[cnt] = min(answer[cnt], cost)
            j -= 1

    for ans in answer:
        print(ans)


if __name__ == '__main__':
    main()


# Optimized solution
# writer解(c++)を写経した．answerのfor文のところ何やってるかさっぱりわかりませんが…
# https://atcoder.jp/contests/m-solutions2020/submissions/15122924
import sys
input = sys.stdin.readline
INF = 10**13


def main():
    N = int(eval(input()))
    T = [[int(i) for i in input().split()] for j in range(N)]
    X_dist = [[0]*N for _ in range(1 << N)]
    Y_dist = [[0]*N for _ in range(1 << N)]

    # bitという道路群を建設したときの，各集落の評価距離
    # bit 001001 とかの1が立っている集落に道を作る
    for bit in range(1 << N):
        cur_x = [0]
        cur_y = [0]
        for i in range(N):
            if bit & (1 << i):
                cur_x.append(T[i][0])
                cur_y.append(T[i][1])
        for i, (x, y, p) in enumerate(T):
            X_dist[bit][i] = p*min(abs(cx - x) for cx in cur_x)
            Y_dist[bit][i] = p*min(abs(cy - y) for cy in cur_y)

    # これはなに？
    answer = [INF] * (N+1)
    for i in range(1 << N):
        cnt = 0
        for j in range(N):
            if (i >> j) & 1:
                cnt += 1
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(N):
                if not((i >> k) & 1):
                    cost += min(X_dist[j][k], Y_dist[i - j][k])
            answer[cnt] = min(answer[cnt], cost)
            j -= 1

    for ans in answer:
        print(ans)


if __name__ == '__main__':
    main()
# Original solution
import sys
input = sys.stdin.readline
INF = 10**13


def main():
    N = int(eval(input()))
    T = [[int(i) for i in input().split()] for j in range(N)]
    X_dist = [[0]*N for _ in range(1 << N)]
    Y_dist = [[0]*N for _ in range(1 << N)]

    for bit in range(1 << N):
        cur_x = [0]
        cur_y = [0]
        for i in range(N):
            if bit & (1 << i):
                cur_x.append(T[i][0])
                cur_y.append(T[i][1])
        for i, (x, y, p) in enumerate(T):
            X_dist[bit][i] = p*min(abs(cx - x) for cx in cur_x)
            Y_dist[bit][i] = p*min(abs(cy - y) for cy in cur_y)

    answer = [INF] * (N+1)
    count = 0
    for i in range(1 << N):
        cnt = bin(i).count("1")
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(N):
                count += 1
                if not((i >> k) & 1):
                    cost += min(X_dist[j][k], Y_dist[i - j][k])
            answer[cnt] = min(answer[cnt], cost)
            j -= 1

    for ans in answer:
        print(ans)


if __name__ == '__main__':
    main()


# Optimized solution
import sys
input = sys.stdin.readline
INF = 10**13


def main():
    N = int(eval(input()))
    T = [[int(i) for i in input().split()] for j in range(N)]
    X_dist = [[0]*N for _ in range(1 << N)]
    Y_dist = [[0]*N for _ in range(1 << N)]

    for bit in range(1 << N):
        cur_x = [0]
        cur_y = [0]
        for i in range(N):
            if bit & (1 << i):
                cur_x.append(T[i][0])
                cur_y.append(T[i][1])
        for i, (x, y, p) in enumerate(T):
            X_dist[bit][i] = p*min(abs(cx - x) for cx in cur_x)
            Y_dist[bit][i] = p*min(abs(cy - y) for cy in cur_y)

    answer = [INF] * (N+1)
    for i in range(1 << N):
        cnt = bin(i).count("1")
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(N):
                if not((i >> k) & 1):
                    cost += min(X_dist[j][k], Y_dist[i - j][k])
            answer[cnt] = min(answer[cnt], cost)
            j -= 1

    for ans in answer:
        print(ans)


if __name__ == '__main__':
    main()
# Original solution
n = int(eval(input()))
towns = [tuple(map(int, input().split())) for _ in range(n)]

INF = 10 ** 18
ans = [INF] * (n + 1)

default_dist = [min(abs(x), abs(y)) for x, y, p in towns]

for bit in range(1 << n):
    k = (bit & 0x5555) + (bit >> 1 & 0x5555)
    k = (k & 0x3333) + (k >> 2 & 0x3333)
    k = (k & 0x0f0f) + (k >> 4 & 0x0f0f)
    k = (k & 0x00ff) + (k >> 8 & 0x00ff)
    i = 0
    t = bit
    selected = []
    is_selected = [False] * n
    while t:
        if t & 1:
            selected.append(towns[i])
            is_selected[i] = True
        t >>= 1
        i += 1

    for bit2 in range(1 << k):
        cost = 0
        for i in range(n):
            if is_selected[i]:
                continue
            town_dist = default_dist[i]
            t = bit2
            x, y, p = towns[i]
            for j in range(k):
                if t & 1:
                    town_dist = min(town_dist, abs(selected[j][1] - y))
                else:
                    town_dist = min(town_dist, abs(selected[j][0] - x))
                t >>= 1
            cost += town_dist * p
        ans[k] = min(ans[k], cost)

print(('\n'.join(map(str, ans))))


# Optimized solution
import sys

n, *towns = list(map(int, sys.stdin.buffer.read().split()))
xxx = towns[0::3]
yyy = towns[1::3]
ppp = towns[2::3]

INF = 10 ** 18
ans = [INF] * (n + 1)

precalc_dist_x = []
precalc_dist_y = []
for bit in range(1 << n):
    dists_x = []
    dists_y = []
    for i in range(n):
        x = xxx[i]
        y = yyy[i]
        dist_x = abs(x)
        dist_y = abs(y)

        t = bit
        j = 0
        while t:
            if t & 1:
                dist_x = min(dist_x, abs(xxx[j] - x))
                dist_y = min(dist_y, abs(yyy[j] - y))
            t >>= 1
            j += 1
        dists_x.append(dist_x * ppp[i])
        dists_y.append(dist_y * ppp[i])
    precalc_dist_x.append(dists_x)
    precalc_dist_y.append(dists_y)

for bit in range(1 << n):
    k = (bit & 0x5555) + (bit >> 1 & 0x5555)
    k = (k & 0x3333) + (k >> 2 & 0x3333)
    k = (k & 0x0f0f) + (k >> 4 & 0x0f0f)
    k = (k & 0x00ff) + (k >> 8 & 0x00ff)
    vertical = bit
    while vertical:
        cost = 0
        pcx = precalc_dist_x[vertical]
        pcy = precalc_dist_y[vertical ^ bit]
        for i in range(n):
            cost += min(pcx[i], pcy[i])
        ans[k] = min(ans[k], cost)
        vertical = (vertical - 1) & bit
    cost = 0
    pcx = precalc_dist_x[0]
    pcy = precalc_dist_y[bit]
    for i in range(n):
        cost += min(pcx[i], pcy[i])
    ans[k] = min(ans[k], cost)

print(('\n'.join(map(str, ans))))
# Original solution
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve():
    xc = [[0] * n for _ in range(1 << n)]
    yc = [[0] * n for _ in range(1 << n)]
    for s in range(1 << n):
        for i,(x, y, p) in enumerate(xyp):
            xcost = abs(x)
            ycost = abs(y)
            for j, (lx, ly, _) in enumerate(xyp):
                if s >> j & 1 == 0: continue
                xcost = min(xcost, abs(x - lx))
                ycost = min(ycost, abs(y - ly))
            xc[s][i] = xcost * p
            yc[s][i] = ycost * p

    ans = [inf] * (n + 1)
    for s in range(1 << n):
        k = bin(s).count("1")
        xs = (1 << n) - 1
        while xs > 0:
            xs &= s
            xcs=xc[xs]
            ycs=yc[s-xs]
            ans[k]=min(ans[k], sum(min(xcs[i], ycs[i]) for i in range(n)))
            xs -= 1

    for a in ans: print(a)

inf = 10 ** 16
n = II()
xyp = LLI(n)

solve()


# Optimized solution
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve():
    xc = [[0] * n for _ in range(1 << n)]
    yc = [[0] * n for _ in range(1 << n)]
    for s in range(1 << n):
        xcs = xc[s]
        ycs = yc[s]
        for i, (x, y, p) in enumerate(xyp):
            xcost = abs(x)
            ycost = abs(y)
            for j, (lx, ly, _) in enumerate(xyp):
                if s >> j & 1 == 0: continue
                if abs(x - lx) < xcost: xcost = abs(x - lx)
                if abs(y - ly) < ycost: ycost = abs(y - ly)
            xcs[i] = xcost * p
            ycs[i] = ycost * p
    # print(xc)

    ans = [inf] * (n + 1)
    for s in range(1 << n):
        k = bin(s).count("1")
        xs = (1 << n) - 1
        while xs > 0:
            xs &= s
            xcs = xc[xs]
            ycs = yc[s - xs]
            cur = 0
            for i in range(n): cur += min(xcs[i], ycs[i])
            if cur < ans[k]: ans[k] = cur
            xs -= 1

    for a in ans: print(a)

inf = 10 ** 16
n = II()
xyp = LLI(n)

solve()