M-SOLUTIONS Programming Contest 2020 - M's Solution

New AtCoder City has an infinite grid of streets, as follows:

* At the center of the city stands a clock tower. Let (0, 0) be the coordinates of this point.
* A straight street, which we will call East-West Main Street, runs east-west and passes the clock tower. It corresponds to the x-axis in the two-dimensional coordinate plane.
* There are also other infinitely many streets parallel to East-West Main Street, with a distance of 1 between them. They correspond to the lines \ldots, y = -2, y = -1, y = 1, y = 2, \ldots in the two-dimensional coordinate plane.
* A straight street, which we will call North-South Main Street, runs north-south and passes the clock tower. It corresponds to the y-axis in the two-dimensional coordinate plane.
* There are also other infinitely many streets parallel to North-South Main Street, with a distance of 1 between them. They correspond to the lines \ldots, x = -2, x = -1, x = 1, x = 2, \ldots in the two-dimensional coordinate plane.



There are N residential areas in New AtCoder City. The i-th area is located at the intersection with the coordinates (X_i, Y_i) and has a population of P_i. Each citizen in the city lives in one of these areas.

The city currently has only two railroads, stretching infinitely, one along East-West Main Street and the other along North-South Main Street.
M-kun, the mayor, thinks that they are not enough for the commuters, so he decides to choose K streets and build a railroad stretching infinitely along each of those streets.

Let the walking distance of each citizen be the distance from his/her residential area to the nearest railroad.
M-kun wants to build railroads so that the sum of the walking distances of all citizens, S, is minimized.

For each K = 0, 1, 2, \dots, N, what is the minimum possible value of S after building railroads?

Constraints

* 1 \leq N \leq 15
* -10 \ 000 \leq X_i \leq 10 \ 000
* -10 \ 000 \leq Y_i \leq 10 \ 000
* 1 \leq P_i \leq 1 \ 000 \ 000
* The locations of the N residential areas, (X_i, Y_i), are all distinct.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
X_1 Y_1 P_1
X_2 Y_2 P_2
:  :  :
X_N Y_N P_N


Output

Print the answer in N+1 lines.
The i-th line (i = 1, \ldots, N+1) should contain the minimum possible value of S after building railroads for the case K = i-1.

Examples

Input

3
1 2 300
3 3 600
1 4 800


Output

2900
900
0
0


Input

5
3 5 400
5 3 700
5 5 1000
5 7 700
7 5 400


Output

13800
1600
0
0
0
0


Input

6
2 5 1000
5 2 1100
5 5 1700
-2 -5 900
-5 -2 600
-5 -5 2200


Output

26700
13900
3200
1200
0
0
0


Input

8
2 2 286017
3 1 262355
2 -2 213815
1 -3 224435
-2 -2 136860
-3 -1 239338
-2 2 217647
-1 3 141903


Output

2576709
1569381
868031
605676
366338
141903
0
0
0

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys
input = sys.stdin.readline

def main():
	n = int(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)
main()


N = int(input())
X = []
Y = []
P = []
for _ in range(N):
	(x, y, p) = map(int, input().split())
	X.append(x)
	Y.append(y)
	P.append(p)
DX = [[0] * N for _ in range(1 << N)]
DY = [[0] * N for _ in range(1 << N)]
for (i, x) in enumerate(X):
	for k in range(1 << N):
		d = abs(x)
		for (j, xx) in enumerate(X):
			if k & 1 << j:
				d = min(d, abs(xx - x))
		DX[k][i] = d * P[i]
for (i, y) in enumerate(Y):
	for k in range(1 << N):
		d = abs(y)
		for (j, yy) in enumerate(Y):
			if k & 1 << j:
				d = min(d, abs(yy - y))
		DY[k][i] = d * P[i]
ANS = [1 << 100] * (N + 1)
PC = [0] * (1 << N)
for i in range(1, 1 << N):
	PC[i] = PC[i ^ 1] + 1 if i % 2 else PC[i // 2]
RA = []
for i in range(1 << N):
	t = []
	for j in range(N):
		if i & 1 << j:
			t.append(j)
	RA.append(t)
mm = (1 << N) - 1
for i in range(1 << N):
	m = i ^ mm
	j = m
	while 1:
		ans = 0
		for k in RA[i ^ j ^ mm]:
			ans += min(DX[i][k], DY[j][k])
		pc = PC[i] + PC[j]
		ANS[pc] = min(ANS[pc], ans)
		if not j:
			break
		j = m & j - 1
print(*ANS, sep='\n')


import sys

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

def main():
	n = int(input())
	li = []
	for _ in range(n):
		(xi, yi, pi) = map(int, input().split())
		li.append([xi, yi, pi])
	li.sort(key=lambda x: x[2], reverse=True)
	xx = [[abs(li[j][0]) for j in range(n)] for i in range(2 ** n)]
	yy = [[abs(li[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(li[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(li[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(li[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(li[j][1] - k))
			yy[i][j] = res
	index_list = [2 ** q for q in range(n)]
	klist = [10 ** 15] * (n + 1)
	klist[n] = 0
	xx = tuple(xx)
	yy = tuple(yy)
	for xyr2 in range(3 ** (n - 1)):
		xyr = xyr2
		(k, xopen, yopen) = (0, 0, 0)
		for index in range(n - 1):
			(xyr, num) = divmod(xyr, 3)
			k += (num + 1) // 2
			xopen += num % 2 * index_list[index]
			yopen += num // 2 * index_list[index]
		for app in range(3):
			(k2, xopen2, yopen2) = (k, xopen, yopen)
			k2 += (app + 1) // 2
			xopen2 += app % 2 * index_list[n - 1]
			yopen2 += app // 2 * index_list[n - 1]
			cost = 0
			for w in range(n):
				cost += min(xx[xopen2][w], yy[yopen2][w]) * li[w][2]
			klist[k2] = min(klist[k2], cost)
	for g in range(n + 1):
		print(klist[g])
main()


n = int(input())
xyp = [list(map(int, input().split())) for i in range(n)]
cost = [10 ** 20] * (1 << n)
cost[0] = 0
for bitt in range(1, 1 << n):
	xx = []
	yy = []
	pp = []
	m = 0
	for i in range(n):
		(x, y, p) = xyp[i]
		if 1 << i & bitt:
			xx.append(x)
			yy.append(y)
			pp.append(p)
			m += 1
	for i in range(m):
		sx = xx[i]
		anss = 0
		for (x, y, p) in zip(xx, yy, pp):
			anss += min(abs(y), abs(x), abs(sx - x)) * p
		cost[bitt] = min(cost[bitt], anss)
	for j in range(m):
		sy = yy[j]
		anss = 0
		for (x, y, p) in zip(xx, yy, pp):
			anss += min(abs(y), abs(x), abs(sy - y)) * p
		cost[bitt] = min(cost[bitt], anss)
dp = [sum((min(abs(xyp[i][0]), abs(xyp[i][1])) * xyp[i][2] for i in range(n) if 1 << i & j)) for j in range(1 << n)]
print(dp[-1])
for j in range(n):
	for i in range((1 << n) - 1, 0, -1):
		x = i
		while x >= 0:
			x &= i
			dp[i] = min(dp[i], dp[i - x] + cost[x])
			x -= 1
	print(dp[-1])


import sys
input = sys.stdin.readline
INF = 10 ** 13

def main():
	N = int(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 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)
main()


import sys
input = sys.stdin.readline
N = int(input())
XYP = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 18

def scores(Xs):
	L = len(Xs)
	dp = [[INF] * (L + 1) for _ in range(L + 1)]
	init = 0
	for (x, p) in Xs:
		init += abs(x) * p
	if L == 0:
		return [0]
	for (ix, (x, p)) in enumerate(Xs):
		dp[ix][0] = init
		score = 0
		for (jx, (y, q)) in enumerate(Xs):
			score += min(abs(y) * q, abs(x - y) * q)
		dp[ix][1] = score
	for k in range(1, L):
		for (ix, (x, p)) in enumerate(Xs):
			for iy in range(ix + 1, L):
				(y, q) = Xs[iy]
				tmp = dp[ix][k]
				for iz in range(ix + 1, L):
					(z, r) = Xs[iz]
					new = abs(z - y)
					pre = min(abs(z), abs(z - x))
					if new < pre:
						tmp += (new - pre) * r
				dp[iy][k + 1] = min(dp[iy][k + 1], tmp)
	ret = [INF] * (L + 1)
	for k in range(L + 1):
		for j in range(L + 1):
			ret[k] = min(dp[j][k], ret[k])
	return ret
ans = [INF] * (N + 1)
for bit in range(1 << N):
	Xs = []
	Ys = []
	for (i, (x, y, p)) in enumerate(XYP):
		if 1 << i & bit:
			Xs.append((x, p))
		else:
			Ys.append((y, p))
	Xs.sort()
	Ys.sort()
	dpx = scores(Xs)
	dpy = scores(Ys)
	for (i, x) in enumerate(dpx):
		for (j, y) in enumerate(dpy):
			ans[i + j] = min(ans[i + j], x + y)
print(*ans, sep='\n')


import sys
N = int(input())
XYP = [list(map(int, input().split())) for _ in range(N)]
bits = 1 << N
xmemo = [sys.maxsize] * (N * bits)
ymemo = [sys.maxsize] * (N * bits)
for b in range(bits):
	for i in range(N):
		xmemo[b * N + i] = min(XYP[i][2] * abs(XYP[i][0]), xmemo[b * N + i])
		ymemo[b * N + i] = min(XYP[i][2] * abs(XYP[i][1]), ymemo[b * N + i])
		if not b & 1 << i:
			continue
		for j in range(N):
			xmemo[b * N + j] = min(XYP[j][2] * abs(XYP[i][0] - XYP[j][0]), xmemo[b * N + j])
			ymemo[b * N + j] = min(XYP[j][2] * abs(XYP[i][1] - XYP[j][1]), ymemo[b * N + j])
ans = [sys.maxsize] * (N + 1)
for b in range(bits):
	b_ = b
	cnt = bin(b_).count('1')
	while b_ >= 0:
		b_ &= b
		yi = b - b_
		tmp = 0
		for i in range(N):
			tmp += min(xmemo[b_ * N + i], ymemo[yi * N + i])
		ans[cnt] = min(ans[cnt], tmp)
		b_ -= 1
for i in range(N + 1):
	print(ans[i])


n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 13
costs = [INF] * n
for (i, (x, y, c)) in enumerate(info):
	costs[i] = c * min(abs(x), abs(y))
OFFSET = n
x_dir = [INF] * ((1 << n) * OFFSET)
y_dir = [INF] * ((1 << n) * OFFSET)
for bit_state in range(1 << n):
	for (i, (xi, yi, c)) in enumerate(info):
		x_dir[bit_state * OFFSET + i] = min(costs[i], x_dir[bit_state * OFFSET + i])
		y_dir[bit_state * OFFSET + i] = min(costs[i], y_dir[bit_state * OFFSET + i])
		if not bit_state >> i & 1:
			continue
		for (j, (xj, yj, c)) in enumerate(info):
			x_dir[bit_state * OFFSET + j] = min(x_dir[bit_state * OFFSET + j], c * abs(yi - yj))
			y_dir[bit_state * OFFSET + j] = min(y_dir[bit_state * OFFSET + j], c * abs(xi - xj))
ans = [INF] * (n + 1)
for bit_state in range((1 << n) - 1):
	x_bit = bit_state
	cnt = bin(bit_state).count('1')
	while x_bit >= 0:
		x_bit &= bit_state
		y_bit = bit_state - x_bit
		tmp = 0
		for i in range(n):
			tmp += min(x_dir[x_bit * OFFSET + i], y_dir[y_bit * OFFSET + i])
		ans[cnt] = min(ans[cnt], tmp)
		x_bit -= 1
ans[-1] = 0
for res in ans:
	print(res)


def main():
	n = int(input())
	xyp = [list(map(int, input().split())) for _ in [0] * n]
	d = []

	def calc(seq):
		m = len(seq)
		dp = [[10 ** 15] * (m + 1) for _ in [0] * (m + 1)]
		dp[0][0] = 0
		for i in range(m):
			s = seq[i][0]
			for j in range(i + 1):
				temp = dp[j][0]
				for (a, b) in seq[:i + 1]:
					temp += min(abs(a), s - a) * b
				dp[j + 1][i + 1] = min(dp[j + 1][i + 1], temp)
				temp2 = 10 ** 15
				for k in range(1, i + 1):
					temp = dp[j][k]
					t = seq[k - 1][0]
					for (a, b) in seq[k:i + 1]:
						temp += min(abs(a), a - t, s - a) * b
					temp2 = min(temp2, temp)
				dp[j + 1][i + 1] = min(dp[j + 1][i + 1], temp2)
		for i in range(m + 1):
			for (a, b) in seq[:m]:
				dp[i][0] += abs(a) * b
			for k in range(1, m + 1):
				t = seq[k - 1][0]
				temp = 0
				for (a, b) in seq[k:m]:
					temp += min(abs(a), a - t) * b
				dp[i][k] += temp
		for i in range(m + 1):
			dp[i] = min(dp[i])
		dp += [0] * (n - m)
		return dp
	xyp.sort()
	for i in range(2 ** n):
		(x_list, y_list) = ([], [])
		for j in range(n):
			(x, y, p) = xyp[j]
			if i & 1:
				x_list.append([x, p])
			else:
				y_list.append([y, p])
			i >>= 1
		y_list.sort()
		d.append([calc(x_list), calc(y_list)])
	ans = [10 ** 15] * (n + 1)
	for (x, y) in d:
		for i in range(n + 1):
			for j in range(n - i + 1):
				ans[i + j] = min(ans[i + j], x[i] + y[j])
	for i in ans:
		print(i)
main()


def solve(N, X, Y, P):
	inf = 10 ** 18
	cnb_N = 2 ** N
	to_x = [[0] * N for _ in range(cnb_N)]
	to_y = [[0] * N for _ in range(cnb_N)]
	for cn in range(cnb_N):
		for n in range(N):
			to_x[cn][n] = abs(X[n]) * P[n]
			to_y[cn][n] = abs(Y[n]) * P[n]
			for n2 in range(N):
				if cn >> n2 & 1:
					to_x[cn][n] = min(to_x[cn][n], abs(X[n] - X[n2]) * P[n])
					to_y[cn][n] = min(to_y[cn][n], abs(Y[n] - Y[n2]) * P[n])
	ans = [inf] * (N + 1)
	for cn in range(cnb_N):
		count = 0
		for i in range(N):
			count += 1 if cn >> i & 1 else 0
		cn2 = cn
		while cn2 >= 0:
			cn2 = cn2 & cn
			subsum = 0
			for n in range(N):
				if not cn >> n & 1:
					subsum += min(to_x[cn - cn2][n], to_y[cn2][n])
			ans[count] = min(ans[count], subsum)
			cn2 -= 1
	for n in range(N + 1):
		print(ans[n])
N = int(input())
(X, Y, P) = ([], [], [])
for _ in range(N):
	tmp = [int(i) for i in input().split()]
	X.append(tmp[0])
	Y.append(tmp[1])
	P.append(tmp[2])
solve(N, X, Y, P)


inf = 10 ** 15

def main():
	import sys
	input = sys.stdin.readline
	N = int(input())
	X = []
	Y = []
	P = []
	for _ in range(N):
		(x, y, p) = map(int, input().split())
		X.append(x)
		Y.append(y)
		P.append(p)
	dx = [[inf] * N for _ in range(1 << N)]
	dy = [[inf] * N for _ in range(1 << N)]
	for i in range(1 << N):
		Xline = [0]
		Yline = [0]
		for j in range(N):
			if i >> j & 1:
				Xline.append(X[j])
				Yline.append(Y[j])
		for j in range(N):
			for (x, y) in zip(Xline, Yline):
				dx[i][j] = min(dx[i][j], abs(x - X[j]))
				dy[i][j] = min(dy[i][j], abs(y - Y[j]))
	ans = [inf] * (N + 1)
	beki = [1 << j for j in range(N)]
	for i in range(3 ** (N - 1)):
		M = i
		k = 0
		ix = iy = 0
		J = []
		for j in range(N - 1):
			(M, m) = divmod(M, 3)
			if m == 0:
				J.append(j)
			elif m == 1:
				k += 1
				ix += beki[j]
			else:
				k += 1
				iy += beki[j]
		for x in range(3):
			kk = k
			ix_ = ix
			iy_ = iy
			if x == 0:
				J.append(N - 1)
			elif x == 1:
				kk += 1
				ix_ += beki[N - 1]
			else:
				kk += 1
				iy_ += beki[N - 1]
			cost = 0
			for j in J:
				p = P[j]
				cost += min(dx[ix_][j], dy[iy_][j]) * p
			ans[kk] = min(ans[kk], cost)
	for c in ans:
		print(c)
main()


N = int(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)]

def calc(A):
	n = len(A)
	A.sort()
	dp = [[INF] * (n + 1) for _ in range(n + 1)]
	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)]
	for j in range(n + 1):
		res[j] = dp[n][j]
	return res
for s in range(1 << N):
	AX = []
	AY = []
	for i in range(N):
		if s >> i & 1 == 1:
			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)


import sys
rl = sys.stdin.buffer.readline
INF = sys.maxsize
N = int(rl())
PS = [tuple(map(int, rl().split())) for i in range(N)]

def bitcount(n):
	n = n - (n >> 1 & 6148914691236517205)
	n = (n & 3689348814741910323) + (n >> 2 & 3689348814741910323)
	n = n + (n >> 4) & 1085102592571150095
	n = n + (n >> 8)
	n = n + (n >> 16)
	n = n + (n >> 32)
	return n & 127

def subsets(s):
	t = s
	while t >= 0:
		t &= s
		yield t
		t -= 1
xcost = [[INF] * N for _ in range(1 << N)]
ycost = [[INF] * N for _ in range(1 << N)]
for i in range(1 << N):
	for j in range(N):
		xcost[i][j] = abs(PS[j][0])
		ycost[i][j] = abs(PS[j][1])
		for k in range(N):
			if i >> k & 1 == 1:
				xcost[i][j] = min(xcost[i][j], abs(PS[j][0] - PS[k][0]))
				ycost[i][j] = min(ycost[i][j], abs(PS[j][1] - PS[k][1]))
for i in range(1 << N):
	for j in range(N):
		xcost[i][j] = xcost[i][j] * PS[j][2]
		ycost[i][j] = ycost[i][j] * PS[j][2]
ans = [INF] * (N + 1)
for i in range(1 << N):
	size = bitcount(i)
	for j in subsets(i):
		cost = 0
		for k in range(N):
			if i >> k & 1 == 0:
				cost += min(xcost[j][k], ycost[i - j][k])
		ans[size] = min(ans[size], cost)
for a in ans:
	print(a)


INF = float('inf')
(N, *XYP) = map(int, open(0).read().split())
XYP = list(zip(*[iter(XYP)] * 3))

def solve(XP):
	M = len(XP)
	XP.sort()
	dp = [[INF] * (M + 1) for _ in range(M + 1)]
	dp[0][0] = 0
	for (i, (x, p)) in enumerate(XP):
		dp[i + 1][0] = dp[i][0] + abs(x) * p
	for (l, dpl) in enumerate(dp[:M]):
		for r in range(l + 1, M + 1):
			val = INF
			for (lx, _) in XP[l:r]:
				cur = 0
				for (x, p) in XP[l:r]:
					cur += p * min(abs(x - lx), abs(x))
				val = min(val, cur)
			for i in range(1, M + 1):
				dp[r][i] = min(dp[r][i], val + dpl[i - 1])
	res = [INF] * (N + 1)
	res[:M + 1] = dp[M]
	return res
A = [INF] * (N + 1)
for state in range(1 << N):
	(XP, YP) = ([], [])
	for (i, (x, y, p)) in enumerate(XYP):
		if state >> i & 1:
			XP.append((x, p))
		else:
			YP.append((y, p))
	(X, Y) = (solve(XP), solve(YP))
	for i in range(N + 1):
		for j in range(N + 1 - i):
			A[i + j] = min(A[i + j], X[i] + Y[j])
for a in A:
	print(a)


def main():
	n = int(input())
	xyp = [list(map(int, input().split())) for i in range(n)]

	def caldp(a):
		n = len(a)
		a.sort()
		dp = [[float('INF')] * (n + 1) for i in range(n + 1)]
		dp[0][0] = 0
		for l in range(n):
			for r in range(l + 1, n + 1):
				now = float('INF')
				for k in range(l, r):
					count = 0
					for i in range(l, r):
						count += abs(a[i][0] - a[k][0]) * a[i][1]
					now = min(now, count)
				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 = [float('INF')] * (n + 1)
		for i in range(n + 1):
			res[i] = dp[-1][i]
		return res
	ans = [float('INF')] * (n + 1)
	for s in range(1 << n):
		lx = []
		ly = []
		for i in range(n):
			if s >> i & 1:
				lx.append((xyp[i][0], xyp[i][2]))
			else:
				ly.append((xyp[i][1], xyp[i][2]))
		lx = caldp(lx)
		ly = caldp(ly)
		for i in range(len(lx)):
			for j in range(len(ly)):
				ans[i + j] = min(ans[i + j], lx[i] + ly[j])
	for i in ans:
		print(i)
main()


import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values():
	return map(int, input().split())

def read_index():
	return map(lambda x: int(x) - 1, input().split())

def read_list():
	return list(read_values())

def read_lists(N):
	return [read_list() for n in range(N)]

def main():
	N = int(input())
	P = read_lists(N)
	C = [1 << 62] * (N + 1)
	CX = [1 << 62] * (N * 2 ** N)
	CY = [1 << 62] * (N * 2 ** N)
	LX = [0] * 2 ** N
	LY = [0] * 2 ** N
	for K in range(2 ** N):
		X = {0}
		Y = {0}
		for i in range(N):
			if K >> i & 1:
				X.add(P[i][0])
				Y.add(P[i][1])
		for (j, (xp, yp, cp)) in enumerate(P):
			for x in X:
				CX[K * N + j] = min(abs(xp - x) * cp, CX[K * N + j])
			for y in Y:
				CY[K * N + j] = min(abs(yp - y) * cp, CY[K * N + j])
		LX[K] = len(X)
		LY[K] = len(Y)
	for T in range(2 ** N):
		p = format(T, '160b').count('1')
		if C[p] == 0:
			continue
		r = 1 << 62
		tx = T
		while True:
			ty = T - tx
			c = 0
			for n in range(N):
				c += min(CX[tx * N + n], CY[ty * N + n])
			r = min(r, c)
			if tx == 0:
				break
			tx = tx - 1 & T
		C[p] = min(C[p], r)
	print('\n'.join(map(str, C)))
main()


N = int(input())
city = []
for i in range(N):
	(x, y, p) = 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])


def main():
	from sys import setrecursionlimit, stdin, stderr
	from os import environ
	from collections import defaultdict, deque, Counter
	from math import ceil, floor
	from itertools import accumulate, combinations, combinations_with_replacement, product
	setrecursionlimit(10 ** 6)
	dbg = (lambda *something: stderr.write('\x1b[92m{}\x1b[0m'.format(str(something) + '\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
	input = lambda : stdin.readline().rstrip()
	LMIIS = lambda : list(map(int, input().split()))
	II = lambda : int(input())
	P = 10 ** 9 + 7
	INF = 10 ** 12
	N = II()
	positions = deque()
	for i in range(N):
		positions.append(LMIIS())
	v = []
	h = []
	for i in range(2 ** N):
		v.append([INF] * N)
		h.append([INF] * N)
	for i in range(2 ** N):
		v_lines = deque([0])
		h_lines = deque([0])
		for j in range(N):
			if 2 ** j & i:
				v_lines.append(positions[j][0])
				h_lines.append(positions[j][1])
		for (j, (x, y, p)) in enumerate(positions):
			min_x = INF
			min_y = INF
			for x_c in v_lines:
				min_x = min(min_x, abs(x_c - x) * p)
			for y_c in h_lines:
				min_y = min(min_y, abs(y_c - y) * p)
			v[i][j] = min_x
			h[i][j] = min_y
	ans = [INF] * (N + 1)
	n_bit_mask = (1 << N) - 1
	for pattern in range(2 ** N):
		cities = [i for i in range(N) if 2 ** i & pattern == 0]
		key = N - len(cities)
		pattern_v = pattern
		pattern_h = 0
		while True:
			sum_diff = 0
			for i in cities:
				sum_diff += min(v[pattern_v][i], h[pattern_h][i])
			ans[key] = min(ans[key], sum_diff)
			if pattern_v == 0:
				break
			pattern_v = pattern_v - 1 & pattern
			pattern_h = pattern - pattern_v
	print('\n'.join(map(str, ans)))
main()


import sys
input = sys.stdin.readline
N = int(input())
P = [list(map(int, input().split())) for i in range(N)]
ANS = [1 << 60] * (N + 1)
ANS[-1] = 0
DP1 = [20000] * N
S = 0
for i in range(N):
	(x, y, p) = P[i]
	DP1[i] = min(abs(x), abs(y))
	S += DP1[i] * p
ANS[0] = S

def dfs(DP, now, used):
	for next_town in range(now, N):
		(x, y, p) = P[next_town]
		DP2 = list(DP)
		S = 0
		for i in range(N):
			DP2[i] = min(DP2[i], abs(P[i][0] - x))
			S += DP2[i] * P[i][2]
		ANS[used + 1] = min(ANS[used + 1], S)
		dfs(DP2, next_town + 1, used + 1)
		DP2 = list(DP)
		S = 0
		for i in range(N):
			DP2[i] = min(DP2[i], abs(P[i][1] - y))
			S += DP2[i] * P[i][2]
		ANS[used + 1] = min(ANS[used + 1], S)
		dfs(DP2, next_town + 1, used + 1)
dfs(DP1, 0, 0)
for i in range(1, N):
	ANS[i] = min(ANS[i], ANS[i - 1])
print(*ANS)


import itertools
N = int(input())
data = []
min_value_0 = 0
for _ in range(N):
	(X, Y, P) = town = tuple(map(int, input().split()))
	data.append(town)
	min_value_0 += min(abs(X), abs(Y)) * P
print(min_value_0)
B = 2 ** N
table_h = []
table_v = []
for b in range(B):
	towns = []
	i = 0
	x = b
	while x > 0:
		if x % 2 == 1:
			towns.append(i)
		x //= 2
		i += 1
	dists_h = []
	dists_v = []
	for i in range(N):
		(X0, Y0, P0) = data[i]
		d_h = abs(X0)
		d_v = abs(Y0)
		for j in towns:
			(X1, Y1, P1) = data[j]
			d_h = min(d_h, abs(X1 - X0))
			d_v = min(d_v, abs(Y1 - Y0))
		dists_h.append(d_h * P0)
		dists_v.append(d_v * P0)
	table_h.append(dists_h)
	table_v.append(dists_v)
table = [min_value_0] * (N + 1)
import sys
stack = [0] * N
i = 0
c = 0
b0 = 0
b1 = 0
b = 1
while True:
	if i == N:
		value = 0
		t1 = table_h[b0]
		t2 = table_v[b1]
		for j in range(N):
			value += min(t1[j], t2[j])
		if table[c] > value:
			table[c] = value
		i -= 1
		b //= 2
	else:
		s = stack[i]
		if s == 3:
			if i == 0:
				break
			else:
				stack[i] = 0
				i -= 1
				b //= 2
		else:
			if s == 0:
				b0 += b
				c += 1
			elif s == 1:
				b0 -= b
				b1 += b
			else:
				b1 -= b
				c -= 1
			stack[i] = s + 1
			i += 1
			b *= 2
for i in range(1, N):
	print(table[i])
print(0)


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main():
	N = int(input())
	Resident = []
	for i in range(N):
		(x, y, p) = map(int, input().split())
		Resident.append((x, y, p))
	minCost = [float('inf')] * (N + 1)
	preCalRange = 1 << N
	horizontalLineDistance = []
	verticalLineDistance = []
	for i in range(preCalRange):
		railRoad = bin(i)[2:]
		railRoad = '0' * (N - len(railRoad)) + railRoad
		horizontalLineDistance.append([])
		verticalLineDistance.append([])
		for j in range(N):
			horizontalLineDistance[i].append(min(abs(Resident[j][0]), abs(Resident[j][1])))
			verticalLineDistance[i].append(min(abs(Resident[j][0]), abs(Resident[j][1])))
			for k in range(N):
				if railRoad[k] == '1' and abs(Resident[j][0] - Resident[k][0]) < horizontalLineDistance[i][j]:
					horizontalLineDistance[i][j] = abs(Resident[j][0] - Resident[k][0])
				if railRoad[k] == '1' and abs(Resident[j][1] - Resident[k][1]) < verticalLineDistance[i][j]:
					verticalLineDistance[i][j] = abs(Resident[j][1] - Resident[k][1])
	power2 = [1]
	for i in range(N):
		power2.append(power2[-1] * 2)
	loopCount = power2[N]
	for i in range(loopCount):
		numNewRailroad = bin(i)[2:].count('1')
		j = i
		while j >= 0:
			j &= i
			goodList1 = horizontalLineDistance[j]
			goodList2 = verticalLineDistance[i - j]
			cost = 0
			for k in range(N):
				cost += Resident[k][2] * min(goodList1[k], goodList2[k])
			if minCost[numNewRailroad] > cost:
				minCost[numNewRailroad] = cost
			j -= 1
	for elem in minCost:
		print(elem)
main()


import sys
read = sys.stdin.read
readline = sys.stdin.readline
(n,) = map(int, readline().split())
xyp = tuple((tuple(map(int, readline().split())) for _ in range(n)))
N = 1 << n
INF = 1 << 60
resx = []
resy = []
for i in range(n):
	(x, y, p) = xyp[i]
	rx = [min(abs(x), abs(y))] * N
	ry = [min(abs(x), abs(y))] * N
	for j in range(n):
		for k in range(1 << j):
			rx[k + (1 << j)] = min(rx[k], abs(x - xyp[j][0]))
			ry[k + (1 << j)] = min(ry[k], abs(y - xyp[j][1]))
	for j in range(N):
		rx[j] *= p
		ry[j] *= p
	resx.append(rx)
	resy.append(ry)
ans = [INF] * (n + 1)
N = 3 ** n
p = tuple((3 ** i for i in range(n + 1)))
rv = [0] * N
rx = [0] * N
ry = [0] * N
for j in range(n):
	for k in range(p[j]):
		rv[k + p[j]] = rv[k + 2 * p[j]] = rv[k]
		rv[k] += 1
		rx[k + p[j]] = rx[k] | 1 << j
		ry[k + p[j]] = ry[k]
		rx[k + 2 * p[j]] = rx[k]
		ry[k + 2 * p[j]] = ry[k] | 1 << j
for mask in range(N):
	v = rv[mask]
	x = rx[mask]
	y = ry[mask]
	r = 0
	for i in range(n):
		r += min(resx[i][x], resy[i][y])
	if r < ans[v]:
		ans[v] = r
for i in ans[::-1]:
	print(i)


import sys
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
import bisect
INF = 1 << 50

def generate_dist_arr(X, Y, P):
	N = len(X)
	dist_arr_x = [[] for _ in range(1 << N)]
	dist_arr_y = [[] for _ in range(1 << N)]
	for j in range(1 << N):
		x_lines_list = [0]
		y_lines_list = [0]
		for k in range(N):
			if j >> k & 1:
				x_lines_list.append(X[k])
				y_lines_list.append(Y[k])
		(dist_xx, dist_yy) = ([INF] * N, [INF] * N)
		x_lines_list = sorted(x_lines_list)
		y_lines_list = sorted(y_lines_list)
		for (idx, x) in enumerate(X):
			v = bisect.bisect_left(x_lines_list, x)
			pre_x = x_lines_list[min(v - 1, 0)]
			post_x = x_lines_list[min(v, len(x_lines_list) - 1)]
			dist_xx[idx] = min(abs(pre_x - x), abs(post_x - x)) * P[idx]
		dist_arr_x[j] = dist_xx
		for (idx, y) in enumerate(Y):
			v = bisect.bisect_left(y_lines_list, y)
			pre_y = y_lines_list[max(v - 1, 0)]
			post_y = y_lines_list[min(v, len(y_lines_list) - 1)]
			dist_yy[idx] = min(abs(pre_y - y), abs(post_y - y)) * P[idx]
		dist_arr_y[j] = dist_yy
	return (dist_arr_x, dist_arr_y)

def calc(val_list):
	val_list = sorted(val_list)
	n = len(val_list)
	dp = [[INF] * (n + 1) for _ in range(n + 1)]
	dp[0][0] = 0
	for l in range(n + 1):
		for r in range(l + 1, n + 1):
			next_dist = INF
			for k in range(l + 1, r + 1):
				sum = 0
				for v in range(l + 1, r + 1):
					sum += abs(val_list[v - 1][0] - val_list[k - 1][0]) * val_list[v - 1][1]
				next_dist = min(next_dist, sum)
			for j in range(n):
				dp[r][j + 1] = min(dp[r][j + 1], dp[l][j] + next_dist)
			sum = 0
			for v in range(l + 1, r + 1):
				sum += abs(val_list[v - 1][0]) * val_list[v - 1][1]
			next_dist = sum
			for j in range(n + 1):
				dp[r][j] = min(dp[r][j], dp[l][j] + next_dist)
	return dp

def run():
	N = int(sysread())
	(X, Y) = ([], [])
	for i in range(1, N + 1):
		(x, y, p) = map(int, sysread().split())
		X.append((x, p))
		Y.append((y, p))
	ans = [INF] * (N + 1)
	for i in range(1 << N):
		x_town_list = []
		y_town_list = []
		for k in range(N):
			if i >> k & 1:
				x_town_list.append(X[k])
			else:
				y_town_list.append(Y[k])
		dp_x = calc(x_town_list)[-1]
		dp_y = calc(y_town_list)[-1]
		for i in range(len(dp_x)):
			for j in range(len(dp_y)):
				val = dp_x[i] + dp_y[j]
				ans[i + j] = min(ans[i + j], val)
	for a in ans:
		print(a)
run()


n = int(input())
XYP = [tuple(map(int, input().split())) for i in range(n)]
X = [x for (x, y, p) in XYP]
Y = [y for (x, y, p) in XYP]
P = [p for (x, y, p) in XYP]
pow2 = [2 ** i for i in range(n + 1)]
DX = [[0] * n for s in range(pow2[n])]
DY = [[0] * n for s in range(pow2[n])]
for s in range(1 << n):
	for i in range(n):
		DX[s][i] = abs(X[i]) * P[i]
		DY[s][i] = abs(Y[i]) * P[i]
		for j in range(n):
			if s & 1 << j:
				DX[s][i] = min(DX[s][i], abs(X[i] - X[j]) * P[i])
				DY[s][i] = min(DY[s][i], abs(Y[i] - Y[j]) * P[i])
BC = [bin(s).count('1') for s in range(pow2[n])]
A = [10 ** 20] * (n + 1)
for sx in range(pow2[n]):
	rx = pow2[n] - 1 ^ sx
	sy = rx
	for _ in range(pow2[n - BC[sx]]):
		sy = sy - 1 & rx
		d = 0
		for i in range(n):
			d += min(DX[sx][i], DY[sy][i])
		c = BC[sx] + BC[sy]
		A[c] = min(A[c], d)
print(*A, sep='\n')


import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)
N = int(readline())
XYP = [list(map(int, readline().split())) for _ in range(N)]
costs = [sys.maxsize] * N
for (i, (x, y, c)) in enumerate(XYP):
	costs[i] = c * min(abs(x), abs(y))
x_cost = [sys.maxsize] * ((1 << N) * N)
y_cost = [sys.maxsize] * ((1 << N) * N)
for bit in range(1 << N):
	for (i, (xi, yi, _)) in enumerate(XYP):
		x_cost[bit * N + i] = min(costs[i], x_cost[bit * N + i])
		y_cost[bit * N + i] = min(costs[i], y_cost[bit * N + i])
		if not bit & 1 << i:
			continue
		for (k, (xk, yk, c)) in enumerate(XYP):
			x_cost[bit * N + k] = min(x_cost[bit * N + k], abs(xi - xk) * c)
			y_cost[bit * N + k] = min(y_cost[bit * N + k], abs(yi - yk) * c)
ans = [sys.maxsize] * (N + 1)
for bit in range(1 << N):
	cnt = bin(bit).count('1')
	bit_ = bit
	while bit_ >= 0:
		bit_ &= bit
		cost = 0
		y_bit = bit - bit_
		for k in range(N):
			cost += min(x_cost[bit_ * N + k], y_cost[y_bit * N + k])
		ans[cnt] = min(ans[cnt], cost)
		bit_ -= 1
for i in range(N + 1):
	print(ans[i])


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
X = []
Y = []
P = []
for _ in range(N):
	(x, y, p) = map(int, readline().split())
	X.append(x)
	Y.append(y)
	P.append(p)
DX = [[0] * N for _ in range(1 << N)]
DY = [[0] * N for _ in range(1 << N)]
for (i, x) in enumerate(X):
	for k in range(1 << N):
		d = abs(x)
		for (j, xx) in enumerate(X):
			if k >> j & 1:
				d = min(d, abs(x - xx))
		DX[k][i] = d * P[i]
for (i, y) in enumerate(Y):
	for k in range(1 << N):
		d = abs(y)
		for (j, yy) in enumerate(Y):
			if k >> j & 1:
				d = min(d, abs(y - yy))
		DY[k][i] = d * P[i]
PC = [0] * (1 << N)
for i in range(1 << N):
	PC[i] = PC[i // 2] + 1 if i % 2 else PC[i // 2]
RA = []
for i in range(1 << N):
	t = []
	for j in range(N):
		if i >> j & 1:
			t.append(j)
	RA.append(t)
INF = 10 ** 31
mm = (1 << N) - 1
ANS = [INF] * (N + 1)
for i in range(1 << N):
	m = i ^ mm
	j = m
	dxi = DX[i]
	pci = PC[i]
	while True:
		dyj = DY[j]
		ans = 0
		for k in RA[i ^ j ^ mm]:
			ans += min(dxi[k], dyj[k])
		pc = pci + PC[j]
		if ans < ANS[pc]:
			ANS[pc] = ans
		if j == 0:
			break
		j = m & j - 1
print(*ANS, sep='\n')


INF = 10 ** 12
N = int(input())
X = [0] * N
Y = [0] * N
P = [0] * N
for i in range(N):
	(X[i], Y[i], P[i]) = 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])


import sys
(n, *towns) = 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 & 21845) + (bit >> 1 & 21845)
	k = (k & 13107) + (k >> 2 & 13107)
	k = (k & 3855) + (k >> 4 & 3855)
	k = (k & 255) + (k >> 8 & 255)
	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)))


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


import sys
input = sys.stdin.readline
INF = 10 ** 13

def main():
	N = int(input())
	X = []
	Y = []
	P = []
	for _ in range(N):
		(a, b, c) = (int(i) for i in input().split())
		X.append(a)
		Y.append(b)
		P.append(c)
	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(X[i])
				cur_y.append(Y[i])
		for i in range(N):
			X_dist[bit][i] = P[i] * min((abs(cx - X[i]) for cx in cur_x))
			Y_dist[bit][i] = P[i] * min((abs(cy - Y[i]) 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)
main()


import sys
input = sys.stdin.readline
N = int(input())
a = [tuple(map(int, input().split())) for _ in range(N)]
table = [0] * N
for k in range(N):
	table[k] = min(abs(a[k][0]), abs(a[k][1])) * a[k][2]
tableudi = [10 ** 12 for _ in range((1 << N) * N)]
tablelri = [10 ** 12 for _ in range((1 << N) * N)]
for i in range(1 << N):
	for j in range(N):
		if i & 1 << j:
			for k in range(N):
				ud = min(abs(a[k][0] - a[j][0]) * a[k][2], table[k])
				lr = min(abs(a[k][1] - a[j][1]) * a[k][2], table[k])
				tableudi[i * N + k] = min(tableudi[i * N + k], ud)
				tablelri[i * N + k] = min(tablelri[i * N + k], lr)
		else:
			for k in range(N):
				tableudi[i * N + k] = min(tableudi[i * N + k], min(abs(a[k][0]), abs(a[k][1])) * a[k][2])
				tablelri[i * N + k] = min(tablelri[i * N + k], min(abs(a[k][0]), abs(a[k][1])) * a[k][2])
res = [10 ** 12] * (N + 1)
for t in range(1 << N):
	i = t + 0
	c = bin(t).count('1')
	while True:
		x = i + 0
		y = t ^ x
		rres = 0
		for j in range(N):
			rres += min(tableudi[x * N + j], tablelri[y * N + j])
		res[c] = min(res[c], rres)
		if i == 0:
			break
		i = i - 1 & t
for r in res:
	print(r)


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


import sys
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 cal(xp):
	res = [inf] * (n + 1)
	xp.sort()
	m = len(xp)
	dp = [[inf] * (m + 1) for _ in range(m + 1)]
	dp[0][0] = 0
	for (l, (x, p)) in enumerate(xp):
		dp[l + 1][0] = dp[l][0] + abs(x) * p
	for l in range(m):
		dpl = dp[l]
		for r in range(l + 1, m + 1):
			dpr = dp[r]
			val = inf
			for (lx, _) in xp[l:r]:
				cur = 0
				for (x, p) in xp[l:r]:
					cur += min(abs(x - lx), abs(x)) * p
				val = min(cur, val)
			for j in range(1, m + 1):
				dpr[j] = min(dpr[j], dpl[j - 1] + val)
	dpm = dp[m]
	for i in range(m + 1):
		res[i] = dpm[i]
	return res
inf = 10 ** 16
n = II()
xyp = LLI(n)
ans = [inf] * (n + 1)
for s in range(1 << n):
	xp = []
	yp = []
	for (i, (x, y, p)) in enumerate(xyp):
		if s >> i & 1:
			xp.append((x, p))
		else:
			yp.append((y, p))
	xc = cal(xp)
	yc = cal(yp)
	for i in range(n + 1):
		for j in range(n + 1 - i):
			ans[i + j] = min(ans[i + j], xc[i] + yc[j])
for a in ans:
	print(a)


from bisect import bisect_left
n = int(input())
xyp = [list(map(int, input().split())) for i in range(n)]
inf = 1 << 63
tate = [[] for i in range(1 << n)]
yoko = [[] for i in range(1 << n)]
state_ind = [[] for i in range(1 << n)]
for state in range(1 << n):
	tmp_x = [0]
	tmp_y = [0]
	for i in range(n):
		if state & 1 << i:
			tmp_x.append(xyp[i][0])
			tmp_y.append(xyp[i][1])
		else:
			state_ind[state].append(i)
	tmp_x.sort()
	tmp_y.sort()
	x_score = [0] * n
	y_score = [0] * n
	nn = len(tmp_x)
	mm = len(tmp_y)
	for (i, (x, y, p)) in enumerate(xyp):
		j = bisect_left(tmp_x, x)
		if j == 0:
			x_m = tmp_x[0] - x
		elif j == nn:
			x_m = x - tmp_x[nn - 1]
		else:
			x_m = min(x - tmp_x[j - 1], tmp_x[j] - x)
		j = bisect_left(tmp_y, y)
		if j == 0:
			y_m = tmp_y[0] - y
		elif j == mm:
			y_m = y - tmp_y[mm - 1]
		else:
			y_m = min(y - tmp_y[j - 1], tmp_y[j] - y)
		x_score[i] = x_m * p
		y_score[i] = y_m * p
	tate[state] = x_score
	yoko[state] = y_score
ans = [inf] * (1 << n)
for state in range(1 << n):
	j = state
	while j >= 0:
		j &= state
		i = state ^ j
		tmp1 = 0
		for k in state_ind[state]:
			if tate[i][k] < yoko[j][k]:
				tmp1 += tate[i][k]
			else:
				tmp1 += yoko[j][k]
			if tmp1 >= ans[state]:
				break
		if tmp1 < ans[state]:
			ans[state] = tmp1
		j -= 1
cnt = [0] * (1 << n)
for i in range(1 << n - 1):
	cnt[2 * i] = cnt[i]
	cnt[2 * i + 1] = cnt[i] + 1
ans_k = [inf] * (n + 1)
for state in range(1 << n):
	k = cnt[state]
	if ans_k[k] > ans[state]:
		ans_k[k] = ans[state]
print(*ans_k, sep='\n')


import sys
read = sys.stdin.read
readline = sys.stdin.readline
(n,) = map(int, readline().split())
xyp = tuple((tuple(map(int, readline().split())) for _ in range(n)))
N = 1 << n
INF = 1 << 60
resx = []
resy = []
for i in range(n):
	(x, y, p) = xyp[i]
	rx = [abs(x)] * N
	ry = [abs(y)] * N
	for j in range(n):
		for k in range(1 << j):
			rx[k + (1 << j)] = min(rx[k], abs(x - xyp[j][0]))
			ry[k + (1 << j)] = min(ry[k], abs(y - xyp[j][1]))
	for j in range(N):
		rx[j] *= p
		ry[j] *= p
	resx.append(rx)
	resy.append(ry)
cnt = [n] * N
for j in range(n):
	for k in range(1 << j):
		cnt[k + (1 << j)] = cnt[k] - 1
ans = [INF] * (n + 1)
for m0 in range(N):
	v = cnt[m0]
	mx = N - 1 & ~m0
	while mx >= 0:
		my = N - 1 ^ m0 ^ mx
		r = 0
		for i in range(n):
			if m0 >> i & 1:
				r += min(resx[i][mx], resy[i][my])
		if r < ans[v]:
			ans[v] = r
		mx = mx - 1 & ~m0
for i in ans:
	print(i)