CodeEff/ECCO huggingface dataset:
# Original solution
import sys
input = sys.stdin.readline
def main():
    n = int(eval(input()))
    l = [list(map(int,input().split())) for i in range(n)]

    xcal = [[0]*n for i in range(1<<n)]
    ycal = [[0]*n for i in range(1<<n)]

    for i in range(1<<n):
        for j in range(n):
            xcal[i][j] = abs(l[j][0])
            ycal[i][j] = abs(l[j][1])
            for k in range(n):
                if (i>>k) & 1:
                    xcal[i][j] = min(xcal[i][j],abs(l[j][0]-l[k][0]))
                    ycal[i][j] = min(ycal[i][j],abs(l[j][1]-l[k][1]))
            
    ans = [float("INF")]*(n+1)

    for i in range(1<<n):
        count = 0
        for j in range(n):
            if i >> j & 1:
                count += 1
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(n):
                if not (i>>k & 1):
                    cost += min(xcal[j][k],ycal[i-j][k])*l[k][2]
            ans[count] = min(ans[count],cost)
            j -= 1

    for i in ans:
        print(i)
if __name__ == "__main__":
    main()

# Optimized solution
import sys
input = sys.stdin.readline
def main():
    n = int(eval(input()))
    l = [list(map(int,input().split())) for i in range(n)]

    xcal = [[0]*n for i in range(1<<n)]
    ycal = [[0]*n for i in range(1<<n)]

    for i in range(1<<n):
        for j in range(n):
            xcal[i][j] = abs(l[j][0])
            ycal[i][j] = abs(l[j][1])
            for k in range(n):
                if (i>>k) & 1:
                    xcal[i][j] = min(xcal[i][j],abs(l[j][0]-l[k][0]))
                    ycal[i][j] = min(ycal[i][j],abs(l[j][1]-l[k][1]))
            xcal[i][j] *= l[j][2]
            ycal[i][j] *= l[j][2]
    ans = [float("INF")]*(n+1)

    for i in range(1<<n):
        count = 0
        for j in range(n):
            if i >> j & 1:
                count += 1
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(n):
                if not (i>>k & 1):
                    cost += min(xcal[j][k],ycal[i-j][k])
                if cost > ans[count]:
                    break
            ans[count] = min(ans[count],cost)
            j -= 1

    for i in ans:
        print(i)
if __name__ == "__main__":
    main()
# Original solution
from itertools import product

def sol():
    N = int(input())
    XYP = [tuple(map(int, input().split())) for _ in range(N)]
    X = [x for x, _, _ in XYP]
    Y = [y for _, y, _ in XYP]
    P = [p for _, _, p in XYP]
    INF = 10**18

    def calcCost(AP, A):
        ret = [[INF] * N for _ in range(1 << N)]
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i, (a, p) in enumerate(AP):
                cost = abs(a)
                for z in useA:
                    cost = min(cost, abs(a - z))
                ret[state][i] = cost * p
        return ret

    costX = calcCost([(x, p) for x, _, p in XYP], X)
    costY = calcCost([(y, p) for _, y, p in XYP], Y)

    ans = [INF] * (N + 1)
    for state in product((0, 1, 2), repeat=N):
        stateX = 0
        stateY = 0
        M = N
        for s in state:
            stateX <<= 1
            stateY <<= 1
            if s == 0: M -= 1
            if s == 1: stateX |= 1
            if s == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for s in map(min, zip(cx, cy)):
            cost += s
            if cost >= ans[M]:
                break
        else:
            ans[M] = cost

    print(*ans, sep='\n')

sol()


# Optimized solution
from itertools import product

def sol():
    N = int(input())
    XYP = [tuple(map(int, input().split())) for _ in range(N)]
    X = [x for x, _, _ in XYP]
    Y = [y for _, y, _ in XYP]
    P = [p for _, _, p in XYP]
    INF = 10**18

    def calcCost(AP, A):
        ret = [[INF] * N for _ in range(1 << N)]
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i, (a, p) in enumerate(AP):
                cost = abs(a)
                for z in useA:
                    cost = min(cost, abs(a - z))
                ret[state][i] = cost * p
        return ret

    costX = calcCost([(x, p) for x, _, p in XYP], X)
    costY = calcCost([(y, p) for _, y, p in XYP], Y)

    ans = [INF] * (N + 1)
    for state in product((0, 1, 2), repeat=N):
        stateX = 0
        stateY = 0
        M = N
        for s in state:
            stateX <<= 1
            stateY <<= 1
            if s == 0: M -= 1
            if s == 1: stateX |= 1
            if s == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
            if cost >= ans[M]:
                break
        else:
            ans[M] = cost

    print(*ans, sep='\n')

sol()
# Original solution
from itertools import product

def sol():
    N = int(input())
    XYP = [tuple(map(int, input().split())) for _ in range(N)]
    X = [x for x, _, _ in XYP]
    Y = [y for _, y, _ in XYP]
    P = [p for _, _, p in XYP]
    INF = 10**18

    def calcCost(AP, A):
        ret = [[INF] * N for _ in range(1 << N)]
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i, (a, p) in enumerate(AP):
                cost = abs(a)
                for z in useA:
                    cost = min(cost, abs(a - z))
                ret[state][i] = cost * p
        return ret

    costX = calcCost([(x, p) for x, _, p in XYP], X)
    costY = calcCost([(y, p) for _, y, p in XYP], Y)

    ans = [INF] * (N + 1)
    for state in product((0, 1, 2), repeat=N):
        stateX = 0
        stateY = 0
        M = N
        for s in state:
            stateX <<= 1
            stateY <<= 1
            if s == 0: M -= 1
            if s == 1: stateX |= 1
            if s == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
            if cost >= ans[M]:
                break
        else:
            ans[M] = cost

    print(*ans, sep='\n')

sol()


# Optimized solution
from itertools import product

def sol():
    N = int(input())
    XYP = [tuple(map(int, input().split())) for _ in range(N)]
    XYP.sort(key=lambda xyp: abs(xyp[0] * xyp[1] * xyp[2]), reverse=True)

    X = [x for x, _, _ in XYP]
    Y = [y for _, y, _ in XYP]
    P = [p for _, _, p in XYP]
    INF = 10**18

    def calcCost(AP, A):
        ret = [[INF] * N for _ in range(1 << N)]
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i, (a, p) in enumerate(AP):
                cost = abs(a)
                for z in useA:
                    cost = min(cost, abs(a - z))
                ret[state][i] = cost * p
        return ret

    costX = calcCost([(x, p) for x, _, p in XYP], X)
    costY = calcCost([(y, p) for _, y, p in XYP], Y)

    ans = [INF] * (N + 1)
    for state in product((0, 1, 2), repeat=N):
        stateX = 0
        stateY = 0
        M = N
        for s in state:
            stateX <<= 1
            stateY <<= 1
            if s == 0: M -= 1
            if s == 1: stateX |= 1
            if s == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
            if cost >= ans[M]:
                break
        else:
            ans[M] = cost

    print(*ans, sep='\n')

sol()
# Original solution
from itertools import product

def sol():
    N = int(input())
    XYP = [tuple(map(int, input().split())) for _ in range(N)]
    XYP.sort(key=lambda xyp: abs(xyp[0] * xyp[1] * xyp[2]), reverse=True)

    X = [x for x, _, _ in XYP]
    Y = [y for _, y, _ in XYP]
    P = [p for _, _, p in XYP]
    INF = 10**18

    def calcCost(AP, A):
        ret = [[INF] * N for _ in range(1 << N)]
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i, (a, p) in enumerate(AP):
                cost = abs(a)
                for z in useA:
                    cost = min(cost, abs(a - z))
                ret[state][i] = cost * p
        return ret

    costX = calcCost([(x, p) for x, _, p in XYP], X)
    costY = calcCost([(y, p) for _, y, p in XYP], Y)

    ans = [INF] * (N + 1)
    for state in product((0, 1, 2), repeat=N):
        stateX = 0
        stateY = 0
        M = N
        for s in state:
            stateX <<= 1
            stateY <<= 1
            if s == 0: M -= 1
            if s == 1: stateX |= 1
            if s == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
            if cost >= ans[M]:
                break
        else:
            ans[M] = cost

    print(*ans, sep='\n')

sol()


# Optimized solution
from itertools import product

def sol():
    N = int(input())
    XYP = [tuple(map(int, input().split())) for _ in range(N)]
    XYP.sort(key=lambda xyp: xyp[2], reverse=True)

    X = [x for x, _, _ in XYP]
    Y = [y for _, y, _ in XYP]
    INF = 10**18

    def calcCost(AP, A):
        ret = [[INF] * N for _ in range(1 << N)]
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i, (a, p) in enumerate(AP):
                cost = abs(a)
                for z in useA:
                    cost = min(cost, abs(a - z))
                ret[state][i] = cost * p
        return ret

    costX = calcCost([(x, p) for x, _, p in XYP], X)
    costY = calcCost([(y, p) for _, y, p in XYP], Y)

    ans = [INF] * (N + 1)
    for state in product((0, 1, 2), repeat=N):
        stateX = 0
        stateY = 0
        M = N
        for s in state:
            stateX <<= 1
            stateY <<= 1
            if s == 0: M -= 1
            if s == 1: stateX |= 1
            if s == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
            if cost >= ans[M]:
                break
        else:
            ans[M] = cost

    print(*ans, sep='\n')

sol()
# Original solution
from itertools import product
from random import randint, seed
from time import time
seed(time())

def sol():
    N = int(input())
    XYP = [tuple(map(int, input().split())) for _ in range(N)]
    XYP.sort(key=lambda xyp: xyp[2], reverse=(randint(0, 3) != 0))

    X = [x for x, _, _ in XYP]
    Y = [y for _, y, _ in XYP]
    INF = 10**18

    def calcCost(AP, A):
        ret = [[INF] * N for _ in range(1 << N)]
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i, (a, p) in enumerate(AP):
                cost = abs(a)
                for z in useA:
                    cost = min(cost, abs(a - z))
                ret[state][i] = cost * p
        return ret

    costX = calcCost([(x, p) for x, _, p in XYP], X)
    costY = calcCost([(y, p) for _, y, p in XYP], Y)

    ans = [INF] * (N + 1)
    for state in product((0, 1, 2), repeat=N):
        stateX = 0
        stateY = 0
        M = N
        for s in state:
            stateX <<= 1
            stateY <<= 1
            if s == 0: M -= 1
            if s == 1: stateX |= 1
            if s == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
            if cost >= ans[M]:
                break
        else:
            ans[M] = cost

    print(*ans, sep='\n')

sol()


# Optimized solution
from itertools import product
INF = 10**18
N = int(input())

def calcCost(AP, A):
    ret = [[INF] * N for _ in range(1 << N)]
    for state in range(1 << N):
        useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
        for i, (a, p) in enumerate(AP):
            cost = abs(a)
            for z in useA:
                cost = min(cost, abs(a - z))
            ret[state][i] = cost * p
    return ret

def sol():
    XYP = [tuple(map(int, input().split())) for _ in range(N)]
    XYP.sort(key=lambda xyp: xyp[2], reverse=True)

    X = [x for x, _, _ in XYP]
    Y = [y for _, y, _ in XYP]

    costX = calcCost([(x, p) for x, _, p in XYP], X)
    costY = calcCost([(y, p) for _, y, p in XYP], Y)

    ans = [INF] * (N + 1)
    for state in product((0, 1, 2), repeat=N):
        stateX = 0
        stateY = 0
        M = N
        for s in state:
            stateX <<= 1
            stateY <<= 1
            if s == 0: M -= 1
            if s == 1: stateX |= 1
            if s == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
            if cost >= ans[M]:
                break
        else:
            ans[M] = cost

    print(*ans, sep='\n')

sol()
# Original solution
import bisect

N=int(eval(input()))
city=[]
for i in range(N):
    x,y,p=list(map(int,input().split()))
    city.append((x,y,p))

xx=[[abs(city[j][0]) for j in range(N)] for i in range(2**N)]
yy=[[abs(city[j][1]) for j in range(N)] for i in range(2**N)]

for i in range(2**N):
    X=[0]
    rest=[]
    for j in range(N):
        if i>>j&1==1:
            X.append(city[j][0])
            xx[i][j]=0
        else:
            rest.append(j)
    for j in rest:
        res=10**15
        for k in X:
            res=min(res,abs(city[j][0]-k))
        xx[i][j]=res

for i in range(2**N):
    Y=[0]
    rest=[]
    for j in range(N):
        if i>>j&1==1:
            Y.append(city[j][1])
            yy[i][j]=0
        else:
            rest.append(j)
    for j in rest:
        res=10**15
        for k in Y:
            res=min(res,abs(city[j][1]-k))
        yy[i][j]=res

ans=[10**15 for i in range(N+1)]
for i in range(3**N):
    rest=i
    X=0
    Y=0
    count=0
    amari=[]
    for j in range(N):
        r=rest%3
        if r==1:
            count+=1
            X+=2**j
        elif r==2:
            count+=1
            Y+=2**j
        else:
            amari.append(j)
        rest//=3
    res=0
    for j in amari:
        x=xx[X][j]
        y=yy[Y][j]
        res+=min(x,y)*city[j][2]
    ans[count]=min(ans[count],res)

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


# Optimized solution
import bisect

N=int(eval(input()))
city=[]
for i in range(N):
    x,y,p=list(map(int,input().split()))
    city.append((x,y,p))

xx=[[abs(city[j][0]) for j in range(N)] for i in range(2**N)]
yy=[[abs(city[j][1]) for j in range(N)] for i in range(2**N)]

for i in range(2**N):
    X=[0]
    rest=[]
    for j in range(N):
        if i>>j&1==1:
            X.append(city[j][0])
            xx[i][j]=0
        else:
            rest.append(j)
    for j in rest:
        res=10**15
        for k in X:
            res=min(res,abs(city[j][0]-k))
        xx[i][j]=res

for i in range(2**N):
    Y=[0]
    rest=[]
    for j in range(N):
        if i>>j&1==1:
            Y.append(city[j][1])
            yy[i][j]=0
        else:
            rest.append(j)
    for j in rest:
        res=10**15
        for k in Y:
            res=min(res,abs(city[j][1]-k))
        yy[i][j]=res

ans=[10**15 for i in range(N+1)]
for i in range(2**N):
    cond=i
    rest=[j for j in range(N) if i>>j &1==0]
    count=N-len(rest)
    while True:
        X=cond
        Y=i-cond
        temp=0
        for j in rest:
            temp+=min(xx[X][j],yy[Y][j])*city[j][2]
        ans[count]=min(ans[count],temp)
        if cond==0:
            break
        else:
            cond=(cond-1)&i

for i in range(N+1):
    print((ans[i]))
# Original solution
import sys
input = sys.stdin.readline

INF = float('inf')

N = int(input().strip())
data = [list(map(int, input().split())) for _ in range(N)]
cost_b = []
cost_D = []
for b in range(1<<N):
  towns = []
  cost = INF
  for i in range(N):
    if (b>>i)&1:
      towns.append(data[i])
  for i in range(len(towns)):
    X = towns[i][0]
    cost = min(cost,sum(abs(towns[j][0]-X)*towns[j][2] for j in range(len(towns))))
  for i in range(len(towns)):
    Y = towns[i][1]
    cost = min(cost,sum(abs(towns[j][1]-Y)*towns[j][2] for j in range(len(towns))))
  if len(towns) == 0:
    cost = 0
  cost_b.append(cost)
  cost_D.append(sum(min(abs(towns[j][0]),abs(towns[j][1]))*towns[j][2] for j in range(len(towns))))

dp = [[INF]*(N+1) for i in range(1<<N)]

for i in range(1<<N):
  dp[i][0] = cost_D[i]
count = 0
for k in range(1,N+1):
  for i in range(1<<N):
    x = i
    while x>=0:
      x &= i
      new = dp[i-x][k-1]+cost_b[x]
      if dp[i][k] > new:
        dp[i][k] = new
      x -= 1
for i in range(N+1):
  print((dp[-1][i]))

# Optimized solution
import sys
input = sys.stdin.readline

INF = float('inf')

N = int(input().strip())
data = [list(map(int, input().split())) for _ in range(N)]
cost_b = []
cost_D = []
for b in range(1<<N):
  towns = []
  cost = INF
  for i in range(N):
    if (b>>i)&1:
      towns.append(data[i])
  for i in range(len(towns)):
    X = towns[i][0]
    cost = min(cost,sum(abs(towns[j][0]-X)*towns[j][2] for j in range(len(towns))))
  for i in range(len(towns)):
    Y = towns[i][1]
    cost = min(cost,sum(abs(towns[j][1]-Y)*towns[j][2] for j in range(len(towns))))
  if len(towns) == 0:
    cost = 0
  cost_b.append(cost)
  cost_D.append(sum(min(abs(towns[j][0]),abs(towns[j][1]))*towns[j][2] for j in range(len(towns))))

dp = [[INF]*(N+1) for i in range(1<<N)]

for i in range(1<<N):
  dp[i][0] = cost_D[i]
count = 0
for k in range(1,N+1):
  for i in reversed(list(range(1<<N))):
    x = i
    while x>=0:
      x &= i
      new = dp[i-x][k-1]+cost_b[x]
      if dp[i][k] > new:
        dp[i][k] = new
      if new == 0:
        break
      x -= 1
for i in range(N+1):
  print((dp[-1][i]))
# Original solution
import sys
input = sys.stdin.readline

INF = float('inf')

N = int(input().strip())
data = [list(map(int, input().split())) for _ in range(N)]
cost_b = []
cost_D = []
for b in range(1<<N):
  towns = []
  cost = INF
  for i in range(N):
    if (b>>i)&1:
      towns.append(data[i])
  for i in range(len(towns)):
    X = towns[i][0]
    cost = min(cost,sum(abs(towns[j][0]-X)*towns[j][2] for j in range(len(towns))))
  for i in range(len(towns)):
    Y = towns[i][1]
    cost = min(cost,sum(abs(towns[j][1]-Y)*towns[j][2] for j in range(len(towns))))
  if len(towns) == 0:
    cost = 0
  cost_b.append(cost)
  cost_D.append(sum(min(abs(towns[j][0]),abs(towns[j][1]))*towns[j][2] for j in range(len(towns))))

dp = [[INF]*(N+1) for i in range(1<<N)]

for i in range(1<<N):
  dp[i][0] = cost_D[i]
count = 0
for k in range(1,N+1):
  for i in range(1<<N):
    x = i
    while x>=0:
      x &= i
      new = dp[i-x][k-1]+cost_b[x]
      if dp[i][k] > new:
        dp[i][k] = new
      if new == 0:
        break
      x -= 1
for i in range(N+1):
  print((dp[-1][i]))


# Optimized solution
import sys
input = sys.stdin.readline

INF = float('inf')

N = int(input().strip())
data = [list(map(int, input().split())) for _ in range(N)]
cost_b = []
cost_D = []
for b in range(1<<N):
  towns = []
  cost = INF
  for i in range(N):
    if (b>>i)&1:
      towns.append(data[i])
  for i in range(len(towns)):
    X = towns[i][0]
    cost = min(cost,sum(abs(towns[j][0]-X)*towns[j][2] for j in range(len(towns))))
  for i in range(len(towns)):
    Y = towns[i][1]
    cost = min(cost,sum(abs(towns[j][1]-Y)*towns[j][2] for j in range(len(towns))))
  if len(towns) == 0:
    cost = 0
  cost_b.append(cost)
  cost_D.append(sum(min(abs(towns[j][0]),abs(towns[j][1]))*towns[j][2] for j in range(len(towns))))

dp = [[INF]*(N+1) for i in range(1<<N)]

for i in range(1<<N):
  dp[i][0] = cost_D[i]
count = 0
for k in range(1,N+1):
  for i in range(1<<N)[::-1]:
    x = i
    while x>=0:
      x &= i
      new = dp[i-x][k-1]+cost_b[x]
      if dp[i][k] > new:
        dp[i][k] = new
      if new == 0:
        break
      x -= 1
for i in range(N+1):
  print((dp[-1][i]))
# Original solution
import sys, queue, math, copy, itertools, bisect, collections, heapq


def main():
    INF = 10 ** 15
    LI = lambda: [int(x) for x in sys.stdin.readline().split()]
    NI = lambda: int(sys.stdin.readline())

    N = NI()
    X = []
    Y = []
    P = []

    for _ in range(N):
        a, b, c = LI()
        X.append(a)
        Y.append(b)
        P.append(c)

    r = []
    for a, b, c in zip(X, Y, P):
        r.append(min(abs(a), abs(b)) * c)

    hor = [copy.copy(r) for _ in range(2 ** N)]
    ver = [copy.copy(r) for _ in range(2 ** N)]

    for i in range(2 ** N):
        k = i
        for b in range(N):
            if k % 2 == 1:
                for j in range(N):
                    hor[i][j] = min(hor[i][j], abs(X[j] - X[b]) * P[j])
                    ver[i][j] = min(ver[i][j], abs(Y[j] - Y[b]) * P[j])
            k //= 2

    ans = [INF] * (N + 1)
    for i in range(3 ** N):
        cnt:int = 0
        bx:int = 0
        by:int = 0
        for b in range(N):
            bx <<= 1
            by <<= 1
            if i % 3 == 1:
                bx += 1
                cnt += 1
            elif i % 3 == 2:
                by += 1
                cnt += 1
            i //= 3
        if ans[cnt] == 0: continue
        s:int = 0
        for b in range(N):
            s += min(hor[bx][b], ver[by][b])
        ans[cnt] = min(ans[cnt], s)
        if ans[cnt] == 0:
            for j in (cnt,N+1):
                ans[cnt] = 0

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()


# Optimized solution
import sys, queue, math, copy, itertools, bisect, collections, heapq


def main():
    INF = 10 ** 15
    LI = lambda: [int(x) for x in sys.stdin.readline().split()]
    NI = lambda: int(sys.stdin.readline())

    N = NI()
    X = []
    Y = []
    P = []

    for _ in range(N):
        a, b, c = LI()
        X.append(a)
        Y.append(b)
        P.append(c)

    r = []
    st = 0
    for a, b, c in zip(X, Y, P):
        r.append(min(abs(a), abs(b)) * c)
        st += r[-1]
    hor = [copy.copy(r) for _ in range(2 ** N)]
    ver = [copy.copy(r) for _ in range(2 ** N)]

    for i in range(2 ** N):
        k = i
        for b in range(N):
            if k % 2 == 1:
                for j in range(N):
                    hor[i][j] = min(hor[i][j], abs(X[j] - X[b]) * P[j])
                    ver[i][j] = min(ver[i][j], abs(Y[j] - Y[b]) * P[j])
            k //= 2

    ans = [st] * (N + 1)
    for i in range(2 ** N):
        cnt = 0
        j = i
        for _ in range(N):
            cnt += j & 1
            j >>= 1

        j = i
        while True:
            s = 0
            for b in range(N):
                s += min(hor[j][b], ver[i-j][b])
            ans[cnt] = min(ans[cnt], s)
            if j == 0: break
            j -= 1
            j &= i

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()