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

H,W=map(int, input().split())
A=[]
for i in range(H):
  A.append(list(input()))
ds=[]
for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      ds.append((i, j))

x=-1
q=[(i, j, 0) for i, j in ds]
while(q):
  (i, j, n)=q[0]
  del q[0]
  x=max(x, n)
  if i > 0 and A[i-1][j] == '.':
    A[i-1][j] = '#'
    q.append((i-1, j, n+1))
  if i < H-1 and A[i+1][j] == '.':
    A[i+1][j] = '#'
    q.append((i+1, j, n+1))
  if j > 0 and A[i][j-1] == '.':
    A[i][j-1] = '#'
    q.append((i, j-1, n+1))
  if j < W-1 and A[i][j+1] == '.':
    A[i][j+1] = '#'
    q.append((i, j+1, n+1))

  
#print(H,W)
#print(A)
#print(ds)
print(x)

### FIXED CODE ###

def f(h, w):
    dt = [[-1, 0], [0, -1], [0, 1], [1, 0]]
    t = [[True] * (w + 2)]
    for _ in range(h):
        t += [[True] + [(c == "#") for c in input()] + [True]]
    t += [[True] * (w + 2)]
    kuro = []
    for i, ti in enumerate(t[1:-1]):
        for j, tij in enumerate(ti[1:-1]):
            if tij:
                kuro+=[(i + 1, j + 1)]
    cnt = -1
    while kuro:
        cnt += 1
        nxt = []
        for i, j in kuro:
            ti=t[i]
            if not ti[j+1]:
                ti[j + 1]=True
                nxt += [(i, j+1)]
            if not ti[j-1]:
                ti[j - 1]=True
                nxt += [(i, j-1)]
            if not t[i - 1][j]:
                t[i - 1][j]=True
                nxt += [(i - 1, j)]
            if not t[i + 1][j]:
                t[i + 1][j]=True
                nxt += [(i + 1, j)]
        kuro = nxt
    print(cnt)
 
 
h, w = map(int, input().split())
f(h, w)
### BUGGY CODE ###

from heapq import heapify,heappop,heappush

N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]

heapify(A)

for j in range(M):
    B = []
    for i in range(BC[j][0]):
        b = heappop(A)
        if b < BC[j][1]:
            b = BC[j][1]
        B.append(b)
    for i in range(BC[j][0]):
        heappush(A,B[i])

print(sum(A))


### FIXED CODE ###

#要修正　方針は合っているようだが・・・
N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]

A.sort()
BC.sort(reverse=True,key = lambda x:x[1])

pt,card,index = 0,BC[0][1],0
while True:
    for i in range(BC[index][0]):
        if pt < N:
            A[pt] = max(A[pt],card)
        else:
            break
        pt += 1

    index += 1
    if index < M:
        card = BC[index][1]
    else:
        break

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

N,K = map(int,input().split())
for i in range(1,10**10):
    if K**i <= N < K**(i+1):
        print(i+1)
        break

### FIXED CODE ###

N,K = map(int,input().split())
if N == 0 or N == 1:
    print(1)
for i in range(1,100):
    if K**i <= N < K**(i+1):
        print(i+1)
        break
### BUGGY CODE ###

import numpy as np
import sys
N, D, A = map(int, input().split())
L = 2 * D
I = np.array(sys.stdin.read().split(), np.int64)
X = I[::2]
H = I[1::2]
sort_ind = np.argsort(X)
X = X[sort_ind]
H = H[sort_ind]
S = np.zeros(N+1, np.int64)

atack = 0
ans = 0
for i in range(N):
	atack += S[i]
	H[i] -= atack
	if H[i] > 0:
		atack_cnt = -(-H[i]//A)
		ans += atack_cnt
		tmp = atack_cnt * A
		S[i+1] += tmp
		ind = np.searchsorted(X,X[i]+L+1,side = 'left')
		S[ind] -= tmp

print(ans)

### FIXED CODE ###

import numpy as np
import sys
N, D, A = map(int, input().split())
L = 2 * D
I = np.array(sys.stdin.read().split(), np.int64)
X = I[::2]
H = I[1::2]
sort_ind = np.argsort(X)
X = X[sort_ind]
H = H[sort_ind]
S = np.zeros(N+1, np.int64)
ind = np.searchsorted(X,X+L+1,side = 'left')

atack = 0
ans = 0
for i in range(N):
	atack += S[i]
	H[i] -= atack
	if H[i] > 0:
		atack_cnt = -(-H[i]//A)
		ans += atack_cnt
		tmp = atack_cnt * A
		S[i+1] += tmp
		S[ind[i]] -= tmp

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

ss = int(input())
t = 0
i = 0
while t < ss:
    t += 9*10**i
    i += 1
tmp = 0
def sumup(x):
    res = 0
    for i in str(x):
        res += int(i)
    return res

while ss >= t-9*10**(i-1) :
    s = sumup(ss)
    if tmp < s:
        tmp = s
    else:
        pass
    ss -= 1

print(tmp)


### FIXED CODE ###

s = input()
cnt = len(s)

if s[0] == "9":
    if s[1:] == "9"*(cnt-1):
        print(9*cnt)
    else:
        print(8+9*(cnt-1))
else:
    if s[1:] == "9"*(cnt-1):
        print(int(s[0]) + 9*(cnt-1))
    else:
        print((int(s[0])-1) + 9*(cnt-1))
### BUGGY CODE ###

# サンプル3
# 6
# 6 5 4 3 2 1
# b=3で2+0+2+4+6+8 = 22 b=4で1+1+3+5+7+9=26
# わからんからコード書いて試す
n = int(input())
a = list(map(int, input().split()))
# for b in range(-10, 10):
#     tmp = 0
#     for i, v in enumerate(a):
#         tmp += abs(v - (b + i + 1))
#     print(f"b={b}, tmp={tmp}")
# でかくても小さくてもダメっぽい
# 三分探索？やったことないしやり方わからんからググる
# めぐる式にこれhttps://qiita.com/ganariya/items/1553ff2bf8d6d7789127をしただけ

ok, ng = -10**9, 10**9 + 1


def calc(b):
    ret = 0
    for i, v in enumerate(a):
        ret += abs(v - (b + i + 1))
    return ret


# なぜかTLEなるのでカウンタを設置してみた
c = 0
while ng - ok > 1 and c < 10000:
    c += 1
    c1 = (2 * ok + ng) // 3
    c2 = (ok + 2 * ng) // 3
    b1, b2 = calc(c1), calc(c2)
    if b1 > b2:
        ok = c1 + 1  # +1のきもちは不明
    else:
        ng = c2

print(calc(ok))


### FIXED CODE ###

# サンプル3
# 6
# 6 5 4 3 2 1
# b=3で2+0+2+4+6+8 = 22 b=4で1+1+3+5+7+9=26
# わからんからコード書いて試す
n = int(input())
a = list(map(int, input().split()))
# for b in range(-10, 10):
#     tmp = 0
#     for i, v in enumerate(a):
#         tmp += abs(v - (b + i + 1))
#     print(f"b={b}, tmp={tmp}")
# でかくても小さくてもダメっぽい
# 三分探索？やったことないしやり方わからんからググる
# めぐる式にこれhttps://qiita.com/ganariya/items/1553ff2bf8d6d7789127をしただけ

ok, ng = -10**9, 10**9 + 1


def calc(b):
    ret = 0
    for i, v in enumerate(a):
        ret += abs(v - (b + i + 1))
    return ret


# なぜかTLEなるのでカウンタを設置してみた
c = 0
while c < 100:
    c += 1
    c1 = (2 * ok + ng) // 3
    c2 = (ok + 2 * ng) // 3
    b1, b2 = calc(c1), calc(c2)
    if b1 > b2:
        ok = c1 + 1  # +1のきもちは不明
    else:
        ng = c2

print(calc(ok))
### BUGGY CODE ###

import sys


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


MOD = 998244353
n = int(input())
xys = []
ys = []
for line in sys.stdin:
    x, y = map(int, line.split())
    xys.append((x, y))
    ys.append(y)
ys.sort()
y_dict = {y: i + 1 for i, y in enumerate(ys)}
xys = [(x, y_dict[y]) for x, y in xys]
xys.sort()
f_bit = Bit(n)
b_bit = Bit(n)
for i in range(1, n + 1):
    b_bit.add(i, 1)

p2d = [1]
for i in range(n):
    p2d.append(p2d[-1] * 2 % MOD)

ans = 0
for i, (x, y) in enumerate(xys):
    b_bit.add(y, -1)
    a = f_bit.sum(y)
    b = i - a
    c = b_bit.sum(y)
    d = (n - i - 1) - c
    f_bit.add(y, 1)
    # print(i, x, y, a, b, c, d)
    tmp = p2d[n - 1]
    tmp += (p2d[a] - 1) * (p2d[d] - 1) * p2d[b] * p2d[c]
    tmp += (p2d[b] - 1) * (p2d[c] - 1) * p2d[a] * p2d[d]
    tmp -= (p2d[a] - 1) * (p2d[b] - 1) * (p2d[c] - 1) * (p2d[d] - 1)
    ans = (ans + tmp) % MOD
print(ans)


### FIXED CODE ###

import sys


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


MOD = 998244353
n = int(input())
xys = []
ys = []
for line in sys.stdin:
    x, y = map(int, line.split())
    xys.append((x, y))
    ys.append(y)
ys.sort()
y_dict = {y: i + 1 for i, y in enumerate(ys)}
xys = [(x, y_dict[y]) for x, y in xys]
xys.sort()
f_bit = Bit(n)
b_bit = Bit(n)
for i in range(1, n + 1):
    b_bit.add(i, 1)

p2d = [1]
for i in range(n):
    p2d.append(p2d[-1] * 2 % MOD)

ans = 0
for i, (x, y) in enumerate(xys):
    b_bit.add(y, -1)
    a = f_bit.sum(y)
    b = i - a
    c = b_bit.sum(y)
    d = (n - i - 1) - c
    f_bit.add(y, 1)
    # print(i, x, y, a, b, c, d)
    pa, pb, pc, pd = p2d[a], p2d[b], p2d[c], p2d[d]
    tmp = p2d[n - 1]
    tmp += (pa - 1) * (pd - 1) * pb * pc
    tmp += (pb - 1) * (pc - 1) * pa * pd
    tmp -= (pa - 1) * (pb - 1) * (pc - 1) * (pd - 1)
    ans = (ans + tmp) % MOD
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0 for i in range(N)]

for j in range(1,N):
    a = []
    for k in range(max(0,j-K),j):
        a.append(abs(h[j]-h[k])+dp[k])
    dp[j] = min(a)

print(dp[-1])





### FIXED CODE ###

def main():
    N,K = map(int,input().split())
    h = list(map(int,input().split()))
    dp = [0]*N
    for i in range(1,N):
        dp[i]= min(abs(h[i]-h[j])+dp[j] for j in range(max(0,i-K),i))
    print(dp[-1])
main()
### BUGGY CODE ###

N = int(input())
n = [int(_) for _ in range(1, N)]
print(sum(n))

### FIXED CODE ###

N = int(input())
n = N - 1
ans = (n + 1) * n
ans //= 2
print(ans)
### BUGGY CODE ###

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

D = []

for _ in range(K):
    L, R = map(int, input().split())

    for i in range(L, R+1):
        D.append(i)

D.sort()

dp = [0] * 300000
dp[1] = 1

for i in range(2, N+1):
    for d in D:
        if i - d < 1:continue
        dp[i] += dp[i-d]
        dp[i] %= 998244353

print(dp[N])

### FIXED CODE ###

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

L, R = [], []

for _ in range(K):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

dp = [0] * 300000
dpsum = [0] * 300000
dp[1] = 1
dpsum[1] = 1

for i in range(2, N+1):
    for j in range(K):
        li = min(L[j], i)
        ri = min(R[j], i + 1)
        dp[i] += dpsum[i - li] - dpsum[i - ri - 1]

    dp[i] %= 998244353
    dpsum[i] = dpsum[i-1] + dp[i]

print(dp[N])
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
for i in range(N):
    ans=a[i]
    for j in range(N):
        ans=ans ^ a[j]
    print(ans)


### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
tot=0
for i in range(N):
    tot=tot^a[i]
for i in range(N):
    print(tot^a[i])
### BUGGY CODE ###

S = input()
Q = int(input())

r = False
for _ in range(Q):
    query = input()
    if query == '1':
        r ^= True
    else:
        _, f, c = query.split()
        front = f == '1'

        if r ^ front:
            S = c + S
        else:
            S = S + c

if r:
    S = S[::-1]

print(S)


### FIXED CODE ###

S = input()
Q = int(input())

r = False
prefix = []
suffix = []
for _ in range(Q):
    query = input()
    if query == '1':
        r ^= True
    else:
        _, f, c = query.split()
        front = f == '1'

        if r ^ front:
            prefix.append(c)
        else:
            suffix.append(c)

if r:
    S = ''.join(suffix[::-1]) + S[::-1] + ''.join(prefix)
else:
    S = ''.join(prefix[::-1]) + S + ''.join(suffix)

print(S)
### BUGGY CODE ###

S = input()
Q = int(input())
for _ in range(Q):
    q = input()
    if len(q)>1:
        _, f, c = q.split()
        f = int(f)
        if f==1:
            S = c+S
        else:
            S = S+c
    else:
        S = S[::-1]
print(S)

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
s = 1
for _ in range(Q):
    q = input()
    if q!='1':
        if (q[2]=='1' and s==1) or (q[2]!='1' and s!=1):
            S.extendleft(q[4])
        else:
            S.extend(q[4])
    else:
        s *= -1
S = ''.join(list(S))
if s==1:
    print(S)
else:
    print(S[::-1])
### BUGGY CODE ###

import statistics
import math
import copy

n = int(input())
x = list(map(int,input().split()))

for i in range(n):
  tmp = copy.copy(x)
  tmp.pop(i)
  print(statistics.median(tmp))


### FIXED CODE ###


n = int(input())
x = list(map(int,input().split()))
sort_x = sorted(x)

mid_1 = sort_x[n//2-1]
mid_2 = sort_x[n//2]

for i in range(n):
  
  if x[i] <= mid_1:
    print(mid_2)
  else:
    print(mid_1)
### BUGGY CODE ###

N, M = map(int, input().split())
dp = [[0 for i in range(M+1)] for j in range(N+1)]
l = [0 for i in range(N)]
for i in range(N):
    A,B = map(int, input().split())
    l[i] = [-A, -B]
l.sort()
for n in range(1, N+1):
    for m in range(n):
        if -l[n-1][0]  + m <= M:
            dp[n][m] = max(dp[n][m], dp[n-1][m-1] - l[n-1][1])
        dp[n][m-1] = max(dp[n][m-1], dp[n-1][m-1])
print(max(dp[N]))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
l = [0 for i in range(N)]

for i in range(N):
    A, B = map(int, input().split())
    l[i] = [A,-B]
l.sort()

tmp = []
ans = 0
j = 0

for i in range(1, M + 1):
    while j < N:
        A, B = l[j][0], -l[j][1]
        memo = [-B, A]
        if A <= i:
            heapq.heappush(tmp, memo)
            j += 1
        else:
            break
    if len(tmp) > 0:
        ans -= heapq.heappop(tmp)[0]
print(ans)
### BUGGY CODE ###

n,k,*a=map(int,open(0).read().split())
if n<=k:
    print(*[n]*n)
    exit()
import copy
for idx in range(k):
    table=[0]*n
    for i in range(n):
        table[max(i-a[i],0)]+=1
        if i+a[i]+1<n:
            table[i+a[i]+1]-=1
    for i in range(1,n):
        table[i]+=table[i-1]
    a=copy.deepcopy(table)
    if a==[n]*n:
        break
print(*a)

### FIXED CODE ###

n,k=[int(j)for j in input().split()]
a=[int(j)for j in input().split()]
if n<=k:
    print(*[n]*n)
    exit()
import copy
for idx in range(k):
    table=[0]*n
    for i in range(n):
        table[max(i-a[i],0)]+=1
        if i+a[i]+1<n:
            table[i+a[i]+1]-=1
    for i in range(1,n):
        table[i]+=table[i-1]
    a=copy.deepcopy(table)
    if a==[n]*n:
        break
print(*a)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
ABC = list(map(int,read().split()))
A = ABC[::3]; B = ABC[1::3]; C = ABC[2::3]

class BIT():
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        
    def get_sum(self,i):
        s = 0
        while i:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i < self.size:
            self.tree[i] += x
            i += i & -i

def Inversion(seq):
    # seqは、1,2,...,Nの順列
    N = len(seq)
    bit = BIT(N)
    inv = N*(N-1)//2
    for x in seq:
        inv -= bit.get_sum(x)
        bit.add(x,1)
    return inv

def get_rank(seq):
    x_to_i = {x:i for i,x in enumerate(sorted(seq))}
    return [1+x_to_i[x] for x in seq]

def solve_x(A,B,C):
    M = (N*(N-1)//2+1)//2 # 必要な交点個数
    U = 2*10**8 + 100 # 交点の座標の上界
    left = -U # 交点の個数の合計が M 個に満たない
    right = U # 交点の個数の合計が M 個以上である
    # x = -inf における y の順序
    order = sorted(range(N),key = lambda i: A[i]/B[i])
    def test(x):
        y = [(C[i]-A[i]*x)/(B[i]) for i in order]
        seq = get_rank(y)
        return Inversion(seq) >= M
    
    for _ in range(60):
        mid = (left + right)/2
        if test(mid):
            right = mid
        else:
            left = mid
    return (left + right)/2

x = solve_x(A,B,C)
y = solve_x(B,A,C)
print(x,y)



### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
ABC = list(map(int,read().split()))
A = ABC[::3]; B = ABC[1::3]; C = ABC[2::3]

class BIT():
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        
    def get_sum(self,i):
        s = 0
        while i:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i < self.size:
            self.tree[i] += x
            i += i & -i

def Inversion(seq):
    # seqは、1,2,...,Nの順列
    N = len(seq)
    bit = BIT(N)
    inv = N*(N-1)//2
    for x in seq:
        inv -= bit.get_sum(x)
        bit.add(x,1)
    return inv

def get_rank(seq):
    x_to_i = {x:i for i,x in enumerate(sorted(seq))}
    return [1+x_to_i[x] for x in seq]

def solve_x(A,B,C):
    M = (N*(N-1)//2+1)//2 # 必要な交点個数
    U = 2*10**8 + 100 # 交点の座標の上界
    left = -U # 交点の個数の合計が M 個に満たない
    right = U # 交点の個数の合計が M 個以上である
    # x = -inf における y の順序
    order = sorted(range(N),key = lambda i: A[i]/B[i])
    def test(x):
        y = [(C[i]-A[i]*x)/(B[i]) for i in order]
        seq = get_rank(y)
        return Inversion(seq) >= M
    
    for _ in range(60):
        mid = (left + right)/2
        if test(mid):
            right = mid
        else:
            left = mid
    return (left + right)/2

x = solve_x(A,B,C)
y = solve_x(B,A,C)
print(x,y)
### BUGGY CODE ###

S=input()
p=0
cnt=0
while(p!=len(S)):
    for i in range(p+3,len(S)+1):
        if int(S[p:i])%2019==0:
            cnt+=1
    p+=1
print(cnt)

### FIXED CODE ###

s=input()
mod=2019
dp=[0]*mod
k=0
t=1
for x in map(int,s[::-1]):
    k+=t*x
    k%=mod
    dp[k]+=1
    t*=10
    t%=mod
print(sum(i*(i-1)//2 for i in dp)+dp[0])
### BUGGY CODE ###

N =int(input())
List = list(map(int, input().split()))
flag = True
res = 0
while flag:
  for i in range(N):
    if List[i] & 2 == 1:
      flag = False
      break
  if not flag:
    res += 1
print(res)

### FIXED CODE ###

N =int(input())
List = list(map(int, input().split()))
flag = True
res = 0
while flag:
  for i in range(N):
    if List[i] % 2 == 1:
      flag = False
      break
    else:
      List[i] = List[i]//2
  if flag:
    res += 1
print(res)
### BUGGY CODE ###

n=int(input())
s=input()
ans=0
for i in range(n-2):
  fir=s[i]
  for j in range(i+1,n-1):
    sec=s[j]
    if sec==fir:
      continue
    off=j-i
    for k in range(j+1,n):
      if k-j==off:
        continue
      thir=s[k]
      if (fir!=sec)and(sec!=thir)and(thir!=fir):
        ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
r=0
g=0
b=0
for i in range(n):
  if s[i]=="R":
    r+=1
  if s[i]=="G":
    g+=1 
  if s[i]=="B":
    b+=1 
ans=r*g*b
for i in range(n-2):
  for j in range(i+1,n-1):
    k=2*j-i
    if k>=n:
      continue
    if s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
      ans-=1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from collections import defaultdict

N, M = map(int, input().split())
A_list = list(map(int, input().split()))

x = defaultdict(int)
y = defaultdict(int)

for i in range(N):
    temp = x.copy()
    x.clear()
    r = A_list[i] % M
    for t in temp.items():
        y[t[0]] = y[t[0]] + t[1]
        x[int(t[0] + r) % M] = t[1]
    x[r] += 1

print(int(x[0] + y[0]))


### FIXED CODE ###

from collections import Counter
import numpy as np


N, M = map(int, input().split())
A = np.array(list(map(int, input().split())))

A = np.cumsum(A) % M
C = Counter(A)

res = 0
for c in C.items():
    if c[1] > 1:
        res += (c[1]*(c[1]-1)) // 2
    if c[0] == 0:
        res += c[1]

print(res)
### BUGGY CODE ###

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

# パターン1
# A = list(enumerate(A))
# A.sort(key = lambda x: x[1])
# for i in range(N):
#     print(A[i][0] + 1, end = " ")

#パターン2
# A = sorted(range(N), key = lambda i: A[i])
# for i in range(N):
#     print(A[i]+1, end = " ")

# パターン3
min_A = sorted(A)
for i in range(N):
    print(A.index(min_A[i]) + 1, end = " ")


### FIXED CODE ###

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

A = list(enumerate(A))
A.sort(key = lambda x: x[1])

for i in range(N):
    print(A[i][0] + 1, end = " ")
### BUGGY CODE ###

from itertools import permutations
N = int(input())
stuff = list(map(int,input().split()))
#stuff = [5, 5, 6, 1, 1, 1]
junban = list(range(N))

max_happness = 0
for subset in permutations(junban):
    happness = 0
    newjunban = (list(subset))
    for i in range(len(junban)):
        happness +=stuff[i]*abs(newjunban[i]-i)
    if happness>max_happness:
        max_happness = happness
print (max_happness)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ABI = sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True)
prev = [0]
for k, (a, i) in enumerate(ABI):
    curr = [0]*(k+2)
    for l in range(k+1):
        curr[l] = max(curr[l], prev[l] + a*abs(N-i-(k-l)))
        curr[l+1] = prev[l]+a*abs(i-l-1)
    prev = curr
print (max(prev))
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ab = [ai + bi for bi in b for ai in a]
ab.sort(reverse=True)
ab = ab[:k]

s = [ci + abi for abi in ab for ci in c]
s.sort(reverse=True)

for si in s[:k]:
    print(si)

### FIXED CODE ###

import sys
input = sys.stdin.readline

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ab = [ai + bi for bi in b[:k] for ai in a[:k]]
ab.sort(reverse=True)

s = [ci + abi for abi in ab[:k] for ci in c[:k]]
s.sort(reverse=True)

for si in s[:k]:
    print(si)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
import numpy as np
 
K = INT()
sum = 0
 
for n in range(1, K+1):
  for m in range(1, K+1):
    for l in range(1, K+1):
      sum += gcd(n, gcd(m, l))
 
print(sum)

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
K = INT()
sum = 0
 
for n in range(K):
  for m in range(K):
    for l in range(K):
      sum += gcd(n+1, gcd(m+1, l+1))
 
print(sum)
### BUGGY CODE ###

class MyList(list):
    def __init__(self):
        self.__init__ = list

    def cmd(self,command):
        if command == 'deleteFirst':
            self.pop(0)
        elif command == 'deleteLast':
            self.pop(-1)
        else:
            ope, num = command.split()
            num = int(num)
            if ope == 'insert':
                self.insert(0,num)
            else:
                if num in self:
                    self.remove(num)


if __name__ == '__main__' :
    l = MyList()
    n = input()
    for i in range(n):
        l.cmd(raw_input())

    for i in range(len(l)-1):
        print l[i],
    print l[-1]

### FIXED CODE ###

from collections import deque

class MyList(deque):
    def __init__(self):
        self.__init__ = deque
        self.d = {'deleteFirst':self.delF, 'deleteLast':self.delL, 'insert':self.insX, 'delete':self.delX}
    def cmd(self,command):
        if ' ' in command:
            ope, num = command.split()
            num = int(num)
            self.d[ope](num)
        else:
            self.d[command]()
            
    def delF(self):
        self.popleft()

    def delL(self):
        self.pop()

    def insX(self,num):
        self.appendleft(num)

    def delX(self,num):
        if num in self:
            self.remove(num)

if __name__ == '__main__' :
    l = MyList()
    n = input()
    
    for i in range(n):
        l.cmd(raw_input())

    q = deque(l)
    for i in range(len(l)-1):
        print q.popleft(),
    print l[-1]