Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n, k = map(int, input().split())
P = list(map(int, input().split()))
A = []
for i in range(n - k + 1):
    A.append(sum(P[i:i + k]))

M = max(A)
ans = (M + k) / 2
print(ans)


### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
P = np.array([0] + list(map(int, input().split())))
C = np.cumsum(P)
#print(C)
M = 0
for i in range(n - k + 1):
    #print(C[i + k],C[i])
    M = max(M, C[i + k] - C[i])

ans = (M + k) / 2
print(ans)
### BUGGY CODE ###

import fractions

N = int(input())
A = list(map(int, input().split()))
gcd_max = 0
for i in range(N):
    a_temp = A[:i]
    a_temp.extend(A[i + 1:])
    gcd_temp = a_temp[0]
    for a in a_temp:
        gcd_temp = fractions.gcd(gcd_temp, a)
        if gcd_temp <= gcd_max:
            break
    else:
        gcd_max = gcd_temp
print(gcd_max)


### FIXED CODE ###

import fractions

N = int(input())
A = list(map(int, input().split()))
L = [0] * N
R = [0] * N
for i in range(0, N - 1):
    L[i + 1] = fractions.gcd(L[i], A[i])
for i in range(N - 1, 0, -1):
    R[i - 1] = fractions.gcd(R[i], A[i])
print(max([fractions.gcd(L[i], R[i]) for i in range(N)]))
### BUGGY CODE ###

import copy

def bfs(x, y):
    global tmp
    global cnt
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] == ".":
            tmp.append((nx, ny))
            maze[nx][ny] = "#"
            cnt += 1
    return tmp

h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
ans = 0
cnt = 0
tmp = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            tmp.append((i, j))
            cnt += 1

while cnt < h * w:
    tmp_ = copy.copy(tmp)
    tmp = []
    while tmp_:
        p = tmp_.pop()
        bfs(p[0], p[1])
    ans += 1
print(ans)

### FIXED CODE ###

import copy

def bfs(x, y):
    global tmp
    global cnt
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] == ".":
            tmp.append((nx, ny))
            maze[nx][ny] = "#"
            cnt += 1
    return tmp

h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
ans = 0
cnt = 0
tmp = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            tmp.append((i, j))
            cnt += 1

while cnt < h * w:
    tmp_ = copy.copy(tmp)
    tmp = []
    while tmp_:
        p = tmp_.pop()
        bfs(p[0], p[1])
    ans += 1
print(ans)
### BUGGY CODE ###

import numpy as np
N = int(input())
s = list(map(int,input().split()))
s = np.array(s)

ans = 0
for c in range(1,N-1):
    ltor = np.cumsum(s[::c])
    rtol = np.cumsum(s[N-1::-c])
    A = N-1-c
    while c < A:
        if A % c == 0 and A + c * (A//c-1) < N-1:
            break
        temp = ltor[(N-1-A)//c] + rtol[(N-1-A)//c]
        ans = max(temp,ans)
        A -= c

print(ans)



### FIXED CODE ###

N = int(input())
s = list(map(int,input().split()))

ans = 0
for c in range(1,N-1):
    ltor = [0]
    for p in s[::c]:
        ltor.append(ltor[-1] + p)
    rtol = [0]
    for p in s[N-1::-c]:
        rtol.append(rtol[-1] + p)
    A = N-1-c
    while c < A:
        if A % c == 0 and A + c * (A//c-1) < N-1:
            break
        ind = (N-1-A)//c+1
        temp = ltor[ind] + rtol[ind]
        ans = max(temp,ans)
        A -= c

print(ans)
### BUGGY CODE ###

A, B = list(map(int,input().split()))
result = A

for i in range(A+1, B+1):
    result = result ^ (i)

print(result)

### FIXED CODE ###

A, B = list(map(int,input().split()))

if A % 2 == 0 and B % 2 == 0:
    diff = (B - A + 1) // 2
    if diff % 2 == 1:
         print(1 ^ B)
    else :
        print(0 ^ B)
elif A % 2 == 0 and B % 2 == 1:
    diff = (B - A + 1) // 2
    if diff % 2 == 1:
        print(1)
    else :
        print(0)
elif A % 2 == 1 and B % 2 == 0:
    diff = (B - A) // 2
    if diff % 2 == 1:
        print(A ^ 1 ^ B)
    else :
        print(A ^ 0 ^ B)
else :
    diff = (B - A) // 2
    if diff % 2 == 1:
        print(A ^ 1)
    else :
        print(A ^ 0)
### BUGGY CODE ###

import numpy as np
from sys import stdin
input = stdin.readline
N = int(input())
A = list(map(int, input().split()))
number = np.zeros(N, dtype = int)
total = 0
for i in range(N):
  tmp = A.count(i + 1)
  total += tmp * (tmp -1) // 2
  number[i] = tmp
A = np.array(A)
for j in range(N):
  print(total - number[A[j]-1] + 1)


### FIXED CODE ###

import numpy as np
from sys import stdin
input = stdin.readline
N = int(input())
A = list(map(int, input().split()))
number = np.zeros(N, dtype = int)
total = 0

dic = {}
a = sorted(A)
now_key = a[0]
value = 1
dic[now_key] = 1
for i in range(1,N):
  if a[i] == now_key:
    value += 1
  else:
    dic[now_key] = value
    if value >= 2:
      total += value * (value-1) // 2
    now_key = a[i]
    value = 1
dic[now_key] = value
if value >= 2:
  total += value * (value-1)//2
for j in A:
  print(total - dic[j] + 1)
### BUGGY CODE ###

_,m,*A=map(int,open(0).read().split());S=l=3*m;D=[0]*l
for a,b in zip(A,A[1:]):
 b+=m*(b<a);k=b-a;S+=k
 if k>1:D[a+2]+=1;D[b+1]-=k;D[b+2]+=k-1
exec(("i=0;"+"D[i]+=D[i-1];i+=1;"*l)*2);print(S-l-max(D[a]+D[a+m]for a in A))

### FIXED CODE ###

n, m = map(int, raw_input().split())
A = map(int, raw_input().split())
S = 0
for i in xrange(n-1):
    S += (m + A[i+1] - A[i]) % m

T = 2*m
D = [0]*(T+10)
data = [0]*(T+1)
def get(i):
    s = 0
    while i:
        s += data[i]
        i -= i & -i
    return s
def add(i, x):
    while i <= T:
        data[i] += x
        i += i & -i

for i in xrange(n-1):
    x = A[i]; y = A[i+1]
    if y < x:
        y += m
    k = y-x
    if k > 1:
        D[x+2] += 1
        D[y+1] -= k
        D[y+2] += k-1
for i in xrange(1, 2*m+5):
    D[i] += D[i-1]
    add(i, D[i])
res = min(S - (get(a) + get(a+m)) for a in A)
print res
### BUGGY CODE ###

import heapq
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            self.rank[x] += (self.rank[x] == self.rank[y])

def kruskal(n, edge):
    ans = 0
    uf = UnionFind(n)
    for i in range(len(edge)):
        d, v, u = heapq.heappop(edge)
        
        if uf.find(v) != uf.find(u):
            uf.union(v, u)
            n -= 1
            ans += d
            if n < 1: return ans
    return ans

n = int(input())
x, y = [None]*n, [None]*n
dist = [[0] * n for _ in range(n)]

for i in range(n):
    a, b = map(int, input().split())
    x[i] = (a, i)
    y[i] = (b, i)

x.sort(key=lambda x:x[0])
y.sort(key=lambda y:y[0])

edge = []
for i in range(n-1):
    heapq.heappush(edge, (x[i+1][0]-x[i][0], x[i][1], x[i+1][1]))
    heapq.heappush(edge, (y[i+1][0]-y[i][0], y[i][1], y[i+1][1]))

del x, y
print(kruskal(n, edge))

### FIXED CODE ###

import heapq
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            self.rank[x] += (self.rank[x] == self.rank[y])

def kruskal(n, edge):
    ans = 0
    uf = UnionFind(n)
    while True:
        d, v, u = heapq.heappop(edge)
        
        if uf.find(v) != uf.find(u):
            uf.union(v, u)
            n -= 1
            ans += d
        if n < 2: return ans
    return ans

n = int(input())
x, y = [None]*n, [None]*n

for i in range(n):
    a, b = map(int, input().split())
    x[i] = (a, i)
    y[i] = (b, i)

x.sort(key=lambda x:x[0])
y.sort(key=lambda y:y[0])

edge = []
for i in range(n-1):
    heapq.heappush(edge, (x[i+1][0]-x[i][0], x[i][1], x[i+1][1]))
    heapq.heappush(edge, (y[i+1][0]-y[i][0], y[i][1], y[i+1][1]))

del x, y
print(kruskal(n, edge))
### BUGGY CODE ###

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

dp = [0] * (N+1)

for i in range(1,N+1):
    if i <= K - 1:
        continue

    if i == K:
        temp = 1
        for j in range(K):
            temp *= A[i-1-j]
        dp[i] = temp
        continue


    dp[i] = int(dp[i-1] / A[i-1-K] * A[i-1])

for k in range(K+1,N+1):
    if dp[k-1] < dp[k]:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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

for i in range(K, N):
    if A[i] > A[i-K]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

A, B, K = map(int, input().split())
for i in range(A, B + 1):
	if i <= A + K - 1 or B - K + 1 <= i:
		print(i)


### FIXED CODE ###

A, B, K = map(int, input().split())
if 2 * K >= B - A + 1:
	for k in range(A, B + 1):
		print(k)
else:
	for i in range(A, A + K):
		print(i)
	for j in range(B - K + 1, B + 1):
		print(j)
### BUGGY CODE ###

import sys
from copy import deepcopy
sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N,x = MI()
A = LI()
B = deepcopy(A)
A += A

ans = sum(B)
for k in range(1,N+1):
    for i in range(N):
        B[i] = min(B[i],A[N+i-k])
        ans = min(ans,sum(B)+k*x)

print(ans)


### FIXED CODE ###

import sys
from copy import deepcopy
sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N,x = MI()
A = LI()
B = deepcopy(A)
A += A

ans = sum(B)
for k in range(1,N+1):
    for i in range(N):
        B[i] = min(B[i],A[N+i-k])
    ans = min(ans,sum(B)+k*x)

print(ans)
### BUGGY CODE ###

N, M = [int(x) for x in input().split()]
AB_list = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: int(x[0]))
h = []
ans = 0
for i in range(1, M+1):
    while(len(AB_list) > 0 and AB_list[0][0] <= i):
        tmp = AB_list.pop(0)
        h.append(tmp[1])
    if (len(h)):
        tmp = max(h)
        h.pop(h.index(tmp))
        ans += tmp
print(ans)


### FIXED CODE ###

import heapq
N, M = [int(x) for x in input().split()]
AB_list = [[] for _ in range(M)]
for _ in range(N):
    A, B = list(map(int, input().split()))
    if (A > M): continue
    AB_list[A-1].append(B)
h = []
ans = 0
for i in range(M):
    for B in AB_list[i]:
        heapq.heappush(h, -B)
    # print(AB_list, h)
    if (len(h)):
        ans += -heapq.heappop(h)
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()

# 大きく求めて引く
ans = S.count("R") * S.count("G") * S.count("B")

for i in range(N-2):
    for k in range(i+2, N):
        if (i+k) % 2 == 0 and set([S[i], S[(i+k)//2], S[k]]) == set(["R", "G", "B"]):
            ans -= 1

print(ans)


### FIXED CODE ###

N = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")

for i in range(N-2):
    for d in range(1, (N-i-1)//2+1):
        if {S[i], S[i+d], S[i+2*d]} == {"R", "G", "B"}:
            ans -= 1

print(ans)
### BUGGY CODE ###

N = int(input())

sum = 0
for i in range(1, N):
    sum += i

print(sum)

### FIXED CODE ###

N = int(input())

sum = (N - 1) * N // 2

print(sum)
### BUGGY CODE ###

import array
import itertools
from collections import defaultdict, deque


def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


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


def solve():
    def fill(queue):
        footsteps = [[None] * width for _ in range(height)]
        for p, s in queue:
            footsteps[p[1]][p[0]] = -1

        while queue:
            p, s = queue.popleft()
            footsteps[p[1]][p[0]] = s

            for x, y in [(p[0] + 1, p[1]), (p[0] - 1, p[1]), (p[0], p[1] + 1), (p[0], p[1] - 1)]:
                if 0 <= x < width and 0 <= y < height and footsteps[y][x] is None:
                    queue.append(((x, y), s + 1))
                    footsteps[y][x] = -1  # placeholder

        return s

    height, width = tuple(input_ints())
    field = [input() for _ in range(height)]
    queue = deque()

    for y, line in enumerate(field):
        for x, c in enumerate(line):
            if c == '#':
                queue.append(((x, y), 0))
    # queue.append(((10, 10), 0))

    return fill(queue)


def main():
    print(solve())


main()


### FIXED CODE ###

import array
import itertools
from collections import defaultdict, deque


def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


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


def solve():
    def fill(queue):
        footsteps = [[None] * width for _ in range(height)]

        for x, y in queue:
            footsteps[y][x] = 0

        s = 0
        while queue:
            queue2 = deque()
            s += 1
            while queue:
                x, y = queue.popleft()

                if x > 0 and footsteps[y][x - 1] is None:
                    queue2.append((x - 1, y))
                    footsteps[y][x - 1] = s
                if x < width - 1 and footsteps[y][x + 1] is None:
                    queue2.append((x + 1, y))
                    footsteps[y][x + 1] = s
                if y > 0 and footsteps[y - 1][x] is None:
                    queue2.append((x, y - 1))
                    footsteps[y - 1][x] = s
                if y < height - 1 and footsteps[y + 1][x] is None:
                    queue2.append((x, y + 1))
                    footsteps[y + 1][x] = s

            queue = queue2

        return s - 1

    height, width = tuple(input_ints())
    field = [input() for _ in range(height)]
    queue = deque()

    for y, line in enumerate(field):
        for x, c in enumerate(line):
            if c == '#':
                queue.append((x, y))
    # queue.append((10, 10))


    return fill(queue)


def main():
    print(solve())


main()
### BUGGY CODE ###

a = input()
q = int(input())

fflag = 1
for i in range(q):
  qi = input()
  if( qi == "1"):
    fflag *= -1 
  else:
    if( fflag == 1 ):
      if( qi[2] == "2" ):
        a += qi[4]
      else:
        a = qi[4] + a
    else:
      if( qi[2] == "2" ):
        a = qi[4] + a
      else:
        a += qi[4]      
    
if( fflag == 1 ):
  print( a )
else:
  print( a[::-1] )	

### FIXED CODE ###

a = input()
q = int(input())

fflag = 0
ato = ""
mae = ""
for i in range(q):
  qi = input()
  if( qi == "1"):
    fflag += 1 
  else:
    if( fflag%2 == 0 ):
      if( qi[2] == "2" ):
        ato += qi[4]
      else:
        mae += qi[4]
    else:
      if( qi[2] == "2" ):
        mae += qi[4]
      else:
        ato += qi[4]      
    
a = mae[::-1] + a + ato    
    
if( fflag%2==0 ):
  print( a )
else:
  print( a[::-1] )
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a.reverse()
mod = 7 + 10**9
leng = 61
data = [[0 for i in range(leng+1)]for j in range(n)]
#pre
for i in range(n):
    k = bin(a[i])
    k = k[::-1]
    for j in range(1, leng+1):
        if j - 1 >= len(k):
            data[i][j] = data[i - 1][j]
            continue
        if k[j - 1] == "1":
            data[i][j] = data[i - 1][j] + 1
        else:
            data[i][j] = data[i-1][j]
ans = 0
a.reverse()
data.reverse()
for i in range(n-1):
    k = bin(a[i])
    k = list(map(int, list(k[:1:-1])))
    k = k + [0 for i in range(leng - len(k))]
    for j in range(leng):
        if k[j] == 1:
            ans += ((n - i - 1) - data[i+1][j+1]) * (2**j)
            ans %= mod
        else:
            ans += data[i+1][j+1] * (2**j)
            ans %= mod
print(ans)

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        #先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    p = [pow(2,leng - 1 - j, mod) for j in range(leng)]
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * p[j]
            else:
                ans += bit_acc[j] * p[j]
            ans %= mod
    print((ans * 500000004) % mod)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# using sort

n = int(input())
count = 0
a = [[0 for i in range(n)] for i in range(3)]

for i in range(3):
    a[i] = [int(x) for x in input().split()]
    a[i].sort()

# Brute force
for i in a[0]:
    for j in a[1]:
        if i < j:
            index = 0
            for k in a[2]:
                if j < k:
                    count += n - index
                    break
                else:
                    index += 1

print(count)

### FIXED CODE ###

import bisect

n = int(input())
count = 0
a = [[0 for i in range(n)] for i in range(3)]

for i in range(3):
    a[i] = [int(x) for x in input().split()]
    a[i].sort()

# Binary Search
for i in a[1]:
    index0_left = bisect.bisect_left(a[0], i)

    index2_right = bisect.bisect_right(a[2], i)

    count += (index0_left -1 + 1)*(n - index2_right)

print(count)
### BUGGY CODE ###

import math
A,B,N = map(int,input().split())
ans,point = 0,0
looked = min(B-1,N)
i = 2
while(looked <= N):
    point = (A*looked)//B - A*(looked//B)
    ans = max(ans,point)
    looked = i*B-1
    i += 1
print(ans)

### FIXED CODE ###

import math
A,B,N = map(int,input().split())
looked = min(B-1,N)
ans = (A*looked)//B - A*(looked//B)
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = []
B = []

for i in range(N):
  tmp_a, tmp_b = map(int, input().split())
  A.append(tmp_a)
  B.append(tmp_b)
  
buy_count = 0
money_count = 0

while True:
  min_a = min(A)
  index_a = A.index(min_a)
  value_b = B[index_a]
  
  while buy_count < M:
    if value_b == 0:  
      A.pop(index_a)
      B.pop(index_a)
      break
    value_b -= 1
    buy_count += 1
    money_count += A[index_a]
  
  if buy_count == M:
    break
  
print(money_count)

### FIXED CODE ###

N, M = map(int, input().split())
data = []

for i in range(N):
  tmp_a, tmp_b = map(int, input().split())
  data.append((tmp_a, tmp_b))

sorted_data = sorted(data, key=lambda x: x[0])
  
buy_count = 0
money_count = 0

while buy_count < M:
  tmp_a = sorted_data[0][0]
  tmp_b = sorted_data[0][1]

  if buy_count + tmp_b < M:
    buy_count += tmp_b
    money_count += tmp_b * tmp_a
    sorted_data.pop(0)
  else:
    while buy_count < M:
      buy_count += 1
      money_count += tmp_a
      
print(money_count)
### BUGGY CODE ###

n, k, q = map(int, input().split())
ini_point = [k] * n
dec_point = [-q] * n
answerer = []
count_ans = []
for i in range(q):
    answerer.append(int(input()))
for i in range(1,n+1):
    count_ans.append(answerer.count(i))
for i in range(n):
    last_point = dec_point[i] + count_ans[i] + ini_point[i]
    if last_point > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n, k, q = map(int, input().split())
point = [k-q]*n
for i in range(q):
    answerer = int(input())-1
    point[answerer] += 1
for i in range(n):
    if point[i] > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n=int(input())
xyp=[list(map(int,input().split()))for _ in range(n)]
ans=[10**20]*(n+1)
ans[0]=sum(min(abs(x),abs(y))*p for x,y,p in xyp)
ans[-1]=0
xx=[[]]
yy=[[]]
for bitt in range(1,1<<n):
    xs=[(10**20,0)]
    ys=[(10**20,0)]
    for i in range(n):
        if bitt&(1<<i):
            xs.append((xyp[i][0],i))
            ys.append((xyp[i][1],i))
    xs.sort()
    ys.sort()
    xx.append(xs)
    yy.append(ys)
for trit in range(3**n):
    z=0
    xbit=0
    ybit=0
    for i in range(n):
        if trit%3==0:z+=1
        if trit%3==1:xbit+=1<<i
        if trit%3==2:ybit+=1<<i
        trit//=3
    anss=[min(abs(x),abs(y))*p for x,y,p in xyp]
    if xbit:
        xs=xx[xbit]
        i=0
        notx=[1]*n
        for x,j in xx[-xbit-1][:-1]:
            while abs(xs[i][0]-x)>abs(xs[i+1][0]-x):i+=1
            anss[j]=min(anss[j],abs(xs[i][0]-x)*xyp[j][2])
            notx[j]=0
        for j in range(n):
            if notx[j]:anss[j]=0
    if ybit:
        ys=yy[ybit]
        i=0
        noty=[1]*n
        for y,j in yy[-ybit-1][:-1]:
            while abs(ys[i][0]-y)>abs(ys[i+1][0]-y):i+=1
            anss[j]=min(anss[j],abs(ys[i][0]-y)*xyp[j][2])
            noty[j]=0
        for j in range(n):
            if noty[j]:anss[j]=0
    ans[n-z]=min(ans[n-z],sum(anss))
print(*ans)


### FIXED CODE ###

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])
### BUGGY CODE ###

import itertools


def main():
    N = int(input())
    A = [list(map(int, input().split(' '))) for _ in range(N)]
    dp = [0 for _ in range(1 << N)]
    for S in range(1, 1 << N):
        group = [r for r in range(N) if (S >> r) & 1 == 1]
        full_score = sum([A[i][j] for i, j in itertools.combinations(group, 2)])
        score = full_score
        T = S
        while (T - 1) & S > 0:
            T = (T - 1) & S
            score = max([score, dp[S ^ T] + dp[T]])
        dp[S] = score
    print(dp[(1 << N) - 1])


if __name__ == '__main__':
    main()

### FIXED CODE ###

import itertools


def main():
    N = int(input())
    A = [list(map(int, input().split(' '))) for _ in range(N)]
    score_list = [0 for _ in range(1 << N)]
    for S in range(1, 1 << N):
        group = [r for r in range(N) if (S >> r) & 1 == 1]
        score_list[S] = sum([A[i][j] for i, j in itertools.combinations(group, 2)])
    dp = [0 for _ in range(1 << N)]
    for S in range(1, 1 << N):
        score = score_list[S]
        T = (S - 1) & S
        while T > 0:
            x = dp[S ^ T] + dp[T]
            score = max(score, x)
            T = (T - 1) & S
        dp[S] = score
    print(dp[(1 << N) - 1])


if __name__ == '__main__':
    main()