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

import sys
sys.setrecursionlimit(10**9)
INF = float('inf')
H,W = map(int,input().split())
s = [input() for _ in range(H)]
cost = [[INF]*W for _ in range(H)]
cost[0][0] = 1
 
def bfs(h,w):
    for dh,dw in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=h+dh<H and 0<=w+dw<W:
            if s[h+dh][w+dw] == '.' and cost[h+dh][w+dw] > cost[h][w]+1:
                cost[h+dh][w+dw] = cost[h][w]+1
                bfs(h+dh,w+dw)
bfs(0,0)
if cost[-1][-1] == INF:
    print(-1)
else:
    ans = H*W-cost[-1][-1]
    for h in range(H):
        ans -= s[h].count('#')
    print(ans)

### FIXED CODE ###

import queue
H,W = map(int,input().split())
maze = [0]*H
for i in range(H):
    maze[i] = input()
inf = float('inf')
d = [[inf for i in range(W)] for i in range(H)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]


def bfs():
    que = queue.Queue()
    que.put((0,0))
    d[0][0] = 0
    while que.qsize():
        p = que.get()
        if p == (H-1,W-1):
            break
        for i in range(4):
            nx = p[0]+dx[i]
            ny = p[1]+dy[i]
            if 0 <= nx and nx <= H-1 and 0 <= ny and ny <= W-1 \
            and maze[nx][ny] != '#' and d[nx][ny] == inf:
                d[nx][ny] = d[p[0]][p[1]] + 1
                que.put((nx,ny))

bfs()

count = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            count += 1

ans = -1
if d[H-1][W-1] != inf:
    ans = H*W-count-1-d[H-1][W-1]
print(ans)
### BUGGY CODE ###

n = int(input())

l = list(map(int,input().split()))
#print(l)

ans = 0
count = 0
sv = []
for i in l:
    sv.append(i)
#    print(sv,i)
    for j in sv:
 #       print(i,j)
        if i <= j:
            count += 1        
    
    if len(sv) == count:
        ans += 1
        
    count = 0
    
print(ans)

### FIXED CODE ###

n = int(input())

l = list(map(int,input().split()))
#print(l)

ans = 0
min_ = 999999
for i in l:
    if i <= min_:
        min_ = i
        ans += 1

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

n, k = map(int, input().split())
p_n = list(map(int, input().split()))
v_n = []

# リストの値を期待値に変換
for i in range(n):
    v_n.append((p_n[i] + 1) / 2)

s = 0
max_s = 0

for i in range(n - k + 1):
    s = sum(v_n[i:i + k])

    if s > max_s:
        max_s = s

print(max_s)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))

s = sum(p[:k])
max_s = s

for i in range(n - k):
    s = s - p[i] + p[i + k]

    if max_s < s:
        max_s = s

print((max_s + k) / 2)
### BUGGY CODE ###

N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
    w[i],v[i]=map(int,input().split())
dp=[[-1 for _ in range(W+1)] for _ in range(N+1)]
for i in range(W+1):
    dp[N][i] = 0
for i in range(0,N)[::-1]:
    for j in range(W+1):
        if j < w[i]:
            dp[i][j]=dp[i+1][j]
        else:
            dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])
print(dp[0][-1])

### FIXED CODE ###

N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
    w[i],v[i]=map(int,input().split())
dp=[[-1 for _ in range(W+1)] for _ in range(N+1)]
for i in range(W+1):
    dp[N][i] = 0
for i in range(0,N)[::-1]:
    for j in range(W+1):
        if j < w[i]:
            dp[i][j]=dp[i+1][j]
        else:
            dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])
print(dp[0][-1])
### BUGGY CODE ###

import heapq

def solve(n,a):
    res = -float('inf')
    for k in range(n,2*n+1):
        a1 = a[:k]
        a2 = [-a[i] for i in range(k,3*n)]

        heapq.heapify(a1)
        heapq.heapify(a2)

        while len(a1) > n:
            heapq.heappop(a1)
        while len(a2) > n:
            heapq.heappop(a2)
        
        tmp = sum(a1) + sum(a2)

        res = max(res,tmp)

    return res

if __name__ == '__main__':
    n = int(input())
    a = list(map(int,input().split()))
    print(solve(n,a))

### FIXED CODE ###

import heapq

def solve(n,a):
    a1 = a[:n]
    a2 = [-a[i] for i in range(2*n,3*n)]

    l = [[0,0] for i in range(n+1)]

    heapq.heapify(a1)
    heapq.heapify(a2)

    l[0][0] = sum(a1)
    l[n][1] = sum(a2)
    
    for k in range(n,2*n):

        heapq.heappush(a1,a[k])
        tmp = heapq.heappop(a1)
        l[k-n+1][0] = l[k-n][0] + a[k] - tmp

        heapq.heappush(a2,-a[3*n-k-1])
        tmp = heapq.heappop(a2)
        l[2*n-k-1][1] = l[2*n-k][1] - a[3*n-k-1] - tmp

    res = -float('inf')

    for ans in l:
        res = max(res,ans[0]+ans[1])

    return res

if __name__ == '__main__':
    n = int(input())
    a = list(map(int,input().split()))
    print(solve(n,a))
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()

for i in range(q):
    li, ri = map(int, input().split())
    t = s[li - 1:ri]
    a_flag = False
    cnt = 0
    for j in range(len(t)):
        if t[j] == 'A':
            a_flag = True
        elif t[j] == 'C':
            if a_flag:
                cnt += 1
                a_flag = False
        else:
            a_flag = False

    print(cnt)


### FIXED CODE ###

n, q = map(int, input().split())
s = input()

t = [0] * (n + 1)
for i in range(n):
    t[i + 1] = t[i] + (1 if s[i:i+2] == 'AC' else 0)

for i in range(q):
    l, r = map(int, input().split())
    print(t[r - 1] - t[l - 1])
### BUGGY CODE ###

import copy
N = int(input())
A = [int(input()) for i in range(N)]

for i in range(len(A)):
  a = copy.deepcopy(A)
  a.pop(i)
  print(sorted(a)[-1])

### FIXED CODE ###

import numpy as np

N = int(input())
A = [int(input()) for i in range(N)]
A = np.array(A)
first = max(A)
arg = A.argsort()
first_idx = arg[-1]
second_idx = arg[-2]
second = A[second_idx]
for i in range(len(A)):
  if i==first_idx:
    print(second)
  else:
    print(first)
### BUGGY CODE ###

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

Asum=[0]
for i in A:
  if Asum[-1]+i>K:break
  Asum.append(Asum[-1]+i)
import numpy as np
Asum=np.array(Asum)
Bsum=[0]
for i in B:
  if Bsum[-1]+i>K:break
  Bsum.append(Bsum[-1]+i)
Bsum=np.array(Bsum)

maxval=len(Asum)-1

tmp=0
lenB=len(Bsum)
lenA=len(Asum)
for i in range(lenA):
  for j in range(lenB):
    j=tmp+j
    if Asum[-i-1]+Bsum[j]>K:
      maxval=max(maxval,len(Asum)-1-i+j-1)
      tmp=j
      break
    elif j==lenB-1:
      maxval=max(maxval,lenA-1-i+j)
      break
print(maxval)


### FIXED CODE ###

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

Asum=[0]
for i in A:
  if Asum[-1]+i>K:break
  Asum.append(Asum[-1]+i)
import numpy as np
Asum=np.array(Asum)
Bsum=[0]
for i in B:
  if Bsum[-1]+i>K:break
  Bsum.append(Bsum[-1]+i)
Bsum=np.array(Bsum)

maxval=len(Asum)-1

tmp=0
lenB=len(Bsum)
lenA=len(Asum)
for i in range(lenA):
  if lenA-1-i+lenB<maxval:break
  for j in range(lenB):
    j=tmp+j
    if Asum[-i-1]+Bsum[j]>K:
      maxval=max(maxval,len(Asum)-1-i+j-1)
      tmp=j
      break
    elif j==lenB-1:
      maxval=max(maxval,lenA-1-i+j)
      break
print(maxval)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import collections

s = collections.deque(input().strip())
num = int(input())
query = [0] * num
for i in range(num):
    query[i] = input().strip()

for q in query:
    if q[0] == '1':
        s.reverse()
    else:
        _, f, c = q.split()
        if f == '1':
            s.appendleft(c)
        else:
            s.append(c)
print(''.join(list(s)))


### FIXED CODE ###

import sys
input = sys.stdin.readline

import collections

s = collections.deque(input().strip())
num = int(input())
query = [0] * num
for i in range(num):
    query[i] = input().strip()

reverse_flag = False
for q in query:
    if q[0] == '1':
        reverse_flag = not reverse_flag
    else:
        _, f, c = q.split()
        if (f == '1' and not reverse_flag) or (f == '2' and reverse_flag):
            s.appendleft(c)
        if (f == '2' and not reverse_flag) or (f == '1' and reverse_flag):
            s.append(c)
if reverse_flag:
    s.reverse()
print(''.join(list(s)))
### BUGGY CODE ###

n = int(input())
an = [int(i) for i in input().split()]
lowe, an_sub = 0, []
for i in range(0, n):
    an_sub = an[0:i + 1]
    if an_sub[i] <= min(an_sub):
        lowe += 1
print(lowe)

### FIXED CODE ###

n = int(input())
an = [int(i) for i in input().split()]
lowe, min_an_sub = 0, an[0]
an_sub = []
for i in range(0, n):
    an_sub.append(an[i])
    min_an_sub = min(min_an_sub, an[i])
    if an_sub[i] <= min_an_sub:
        lowe += 1
print(lowe)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
l = sorted(l)
ans = 0
for i in range(n):
	    for j in range(i+1,n):
	    	    bottom  = j
	    	    top = n
	    	    while top -bottom > 1:
	    	    	    middle = (top+bottom)//2
	    	    	    if l[middle] <l[i]+l[j]:
	    	    	    	    bottom = middle
	    	    	    else:
	    	    	    	    top = middle
	    	    ans += bottom - j 
print(ans)

### FIXED CODE ###

import bisect
N = int(input())
ans = 0
L = list(map(int,input().split()))
L = sorted(L)
for i in range(N-1):
    for j in range(i+1,N):
        a = bisect.bisect(L,L[i]+L[j]-1)
       
        ans += a-j-1

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

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

ans=[0]*N
D=[[0]*N for _ in range(N)]
graph=[[] for _ in range(N)]
for i in range(M):
  L,R,d=map(int,input().split())
  L,R=L-1,R-1
  ans[R]=ans[L]+d
  graph[L].append([R,d])
  graph[R].append([L,-d])

for i in range(N):
  for j,d in graph[i]:
    if ans[j]-ans[i]!=d:
      print("No")
      exit()
    else:
      continue

print("Yes")

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

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

for _ in range(M):
  l,r,d=map(int,input().split())
  l,r=l-1,r-1
  graph[l].append([r,d])
  graph[r].append([l,-d])

def BFD(x):
  global checked,answer,graph
  checked[x]=1
  for i,distance in graph[x]:
    if answer[i]=="first":
      answer[i]=answer[x]+distance
    else:
      if answer[i]!=answer[x]+distance:
        print("No")
        exit()
    
    if checked[i]==0:
      BFD(i)

checked=[0]*N
answer=["first"]*N

for i in range(N):
  if checked[i]==0:
    answer[i]=0
    BFD(i)

print("Yes")
### BUGGY CODE ###

n = int(input())
s = list(input())
t = []
ans = 0
for i in range(1000):
    t.append(str(i//100))
    t.append(str(i//10%10))
    t.append(str(i%10))
    flg = 0
    for j in range(n):
        if t[flg] == s[j]:
            flg += 1
            if flg == 3:
                ans += 1
                break
    t.clear()
print(ans)

### FIXED CODE ###

n = int(input())
s = list(input())
t = []
ans = 0
for i in range(1000):
    t.append(str(i//100))
    t.append(str(i//10%10))
    t.append(str(i%10))
    k = 0
    p = 0
    for j in range(3):
        if t[j] in s[k:]:
            p = s[k:].index(t[j]) + 1
            k += p
        else:
            p = -1
            break
    if p != -1:
        ans += 1
    t.clear()
print(ans)
### BUGGY CODE ###

H,N = map(int,input().split())
magic = []
for i in range(N):
  a,b = map(int,input().split())
  magic.append((a,b))
A = [item[0] for item in magic]
maxA = max(A)
minA = min(A)
dp = [float("inf")]*(H+maxA+1)
dp[0]=0

for i in range(H+maxA):
  for j in range(N):
    dp[i] = min(dp[i],
                dp[max(i-magic[j][0],0)]+magic[j][1])

print(dp[H])

### FIXED CODE ###

H,N = map(int,input().split())
magic = []
for i in range(N):
  a,b = map(int,input().split())
  magic.append((a,b))
A = [item[0] for item in magic]
maxA = max(A)
minA = min(A)
dp = [float("inf")]*(H+maxA+1)
dp[0]=0
for i in range(H+maxA):
  for j in range(N):
    dp[i] = min(dp[i],
                dp[max(i-magic[j][0],0)]+magic[j][1])
print(dp[H])
### BUGGY CODE ###

from collections import deque

s = input()
d = deque()
li = list(s)
for i in li:
    d.append(i)
n = int(input())
for _ in range(n):
    q = input().split()
    if (len(q)==1):
        d.reverse()
    else:
        a = int(q[1])
        b = q[2]
        if (a == 1):
            d.appendleft(b)
        else:
            d.append(b)
ans = list(d)
xxx = ""
for i in ans:
    xxx += i
print(xxx)
    


### FIXED CODE ###

from collections import deque

s = input()
d = deque(s)
n = int(input())
flag = 0
for _ in range(n):
    q = input().split()
    if (len(q)==1):
        if(flag == 0):
            flag = 1
        else:
            flag = 0
    else:
        a = int(q[1])
        b = q[2]
        if (a == 1):
            if flag==0:
                d.appendleft(b)
            else:
                d.append(b)
        else:
            if flag==0:
                d.append(b)
            else:
                d.appendleft(b)

if flag==1:
    d.reverse()
ans = list(d)
xxx = "".join(ans)
print(xxx)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())

as_ = []
for i in range(h):
    a = [s for s in input().split()]
    for a_ in a:
        as_.append(a_)

ds = [[None]*w for _ in range(h)]
# ds = [[None]*w]*h ←これだとうまくいかないので注意

starts = deque()
for i, a in enumerate(as_):
    for j, a_ in enumerate(a):
        if a_ == "#":
            ds[i][j] = 0
            starts.append((i,j))
def bfs(starts, ds):
    d = 0
    while starts:
        i, j = starts.popleft()
        d = ds[i][j]
        for mx, my in [(0,1),(1,0),(-1,0),(0,-1)]:
            ni = i + my
            nj = j + mx
            if 0 <= ni < h and 0 <= nj < w:
                if ds[ni][nj] == None:
                    ds[ni][nj] = d + 1
                    starts.append((ni, nj))
    return d
d = bfs(starts, ds)
print(d)
### BUGGY CODE ###

s=input()
l=len(s)
k=int(input())
alp=[chr(i) for i in range(97, 97+26)]
ans=set()
for i in range(26):
    for j in range(l):
        if s[j]==alp[i]:
            for m in range(j,l):
                ans.add(s[j:m+1])
    if len(ans)>=k:
        break
print(sorted(list(ans))[k-1])

### FIXED CODE ###

s=input()
l=len(s)
k=int(input())
x=set()
for i in range(1,min(l,k)+1):
    for j in range(l-i+1):
        x.add(s[j:j+i])
x=sorted(list(x))
print(x[k-1])
### BUGGY CODE ###

import collections

def A_sum(A):
  s = 0
  for i in A.items():
    s+=i[0]*i[1]
  print(s)

def A_rep(A,f,t):
  f_num = A.get(f)
  if f_num != None:
      A[t]=A.get(t,0) + f_num
      A.pop(f)

N = int(input())
A = collections.Counter(map(int,input().split()))
Q = int(input())
for i in range(Q):
  b,c = map(int,input().split())
  A_rep(A,b,c)
  A_sum(A)


### FIXED CODE ###

import collections

def A_sum(A):
  s = 0
  for i in A.items():
    s+=i[0]*i[1]
  return s

def A_rep(A,f,t):
  f_num = A.get(f)
  if f_num != None:
      A[t]=A.get(t,0) + f_num
      diff = f_num*(t-f)
      A.pop(f)
      return diff
  return 0

N = int(input())
A = collections.Counter(map(int,input().split()))
Q = int(input())
ans = A_sum(A)
for i in range(Q):
  b,c = map(int,input().split())
  diff = A_rep(A,b,c)
  if diff !=0:
    ans+=diff
  print(ans)
### BUGGY CODE ###

K = int(input())

def gcd(n,m,l):
    if n < m :
        n , m = m , n
    while n % m != 0 :
        n , m = m , n % m
    
    if m < l :
        m , l = l , m
    while m % l != 0 :
        m , l = l , m % l
    
    return l
  
S = 0

for a in range (1, K + 1):
    for b in range (1, K + 1):
        for c in range (1, K + 1):
            S += gcd(a, b, c)

print ( S )
    

### FIXED CODE ###

K = int(input())

def gcd(n,m,l):
    if n < m :
        n , m = m , n
    while n % m != 0 :
        n , m = m , n % m
    
    if m < l :
        m , l = l , m
    while m % l != 0 :
        m , l = l , m % l
    
    return l
  
S = 0

for a in range (1, K + 1):
    for b in range (1, K + 1):
        for c in range (1, K + 1):
            S += gcd(a, b, c)

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

import string
s = input()
k = int(input())
d=[]
for sp in string.ascii_lowercase:
  for i,sd in enumerate(s,start=0):
    if sp == sd:
      for l in range(1, len(s)+1):
        if i+l > len(s):
          break
        d.append(s[i:i+l])
  d=list(set(d))
  if len(d) >= k:
    break

d=list(set(d))
d=sorted(d)
print(d[k-1])

### FIXED CODE ###

import string
s = input()
k = int(input())
d=set()
for sp in string.ascii_lowercase:
  for i,sd in enumerate(s,start=0):
    if sp == sd:
      e=set()
      for l in range(1, 6):
        if i+l > len(s):
          break
        e.add(s[i:i+l])
      d=d|e
  if len(d) >= k:
    break

d=list(d)
d=sorted(d)
print(d[k-1])
### BUGGY CODE ###

N = int(input())
S = [input() for i in range(N)]
count = N

for i in range(N-1):
  for j in range(i+1, N):
    if S[i] == S[j]:
      count -= 1
      break
      
print(count)


### FIXED CODE ###

N = int(input())
list=[]
for _ in range(N):
  S = input()
  list.append(S)
print(len(set(list)))
### BUGGY CODE ###

from itertools import groupby

[H, W] = map(int, input().split())
Ss = [list(map( lambda x: int(x == "."), list(input()) )) for _ in range(H)]

w_count = [[] for _ in range(H)]
for i in range(H):
    for x in groupby(Ss[i]):
        k = len(list(x[1]))
        for _ in range(k):
            w_count[i].append(k * x[0])

h_count = [[0 for _ in range(W)] for _ in range(H)]
for j in range(W):
    i = 0
    for x in groupby([Ss[i][j] for i in range(H)]):
        k = len(list(x[1]))
        for _ in range(k):
            h_count[i][j] = k * x[0]
            i += 1

res = max([max([w_count[i][j] + h_count[i][j] - Ss[i][j] for j in range(W)]) for i in range(H)])

print(res)


### FIXED CODE ###

from itertools import groupby
 
[H, W] = map(int, input().split())
Ss = [list(map( lambda x: int(x == "."), list(input()) )) for _ in range(H)]
 
res = 0
count = [[-Ss[i][j] for j in range(W)] for i in range(H)]
for i in range(H):
    j = 0
    for x in groupby(Ss[i]):
        k = len(list(x[1]))
        for _ in range(k):
            count[i][j] += k * x[0]
            j += 1

for j in range(W):
    i = 0
    for x in groupby([Ss[i][j] for i in range(H)]):
        k = len(list(x[1]))
        for _ in range(k):
            new_res = count[i][j] + k * x[0]
            if res < new_res:
                res = new_res
            i += 1

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

#!/usr/bin/python3
# -*- coding: utf-8 -*-
import sys
import bisect
from collections import deque



def main():
  ## input
  N,Q = map(int, input().split())
  STX = [[0,0,0] for i in range(N)]
  for i in range(N):
    s,t,x = map(int, input().split())
    STX[i] = [s-x, t-x-1, x]
  STX = sorted(STX, key=lambda x:x[2])
  Dn = [int(input()) for _ in range(Q)]+[10**10]

  ans = deque()
  for s,t,x in STX:
    l = bisect.bisect_left(Dn,s)
    r = bisect.bisect_right(Dn,t)-1
    for i in range(r,l-1,-1):
      if Dn[i]>=s and Dn[i]<=t:
        ans.append([Dn[i],x])
        Dn.pop(i)
  for d in Dn:
    ans.append([d,-1])
  
  ret = [x[1] for x in sorted(list(ans))[:-1]]
  return ret


if __name__ == "__main__":
  ans = main()
  [print(a) for a in ans]

### FIXED CODE ###

import sys
from bisect import bisect_left



N,Q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:N]:
  s, t, x = map(int, line.split())
  kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[N:]))

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in kkk:
  ss = bisect_left(ddd, s - x)
  tt = bisect_left(ddd, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

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

import sys
# def input(): return sys.stdin.readline().rstrip()
# input = sys.stdin.readline
input = sys.stdin.buffer.readline

N = int(input())
A = sorted(zip(map(int, (input().split())) ,range(N)), reverse=True)

dp = [[0]*(N+1) for _ in range(N+1)]
ans = 0
for i in range(N):
    for j in range(i+1):
        dp[i+1][j]   = max(dp[i+1][j], dp[i][j] + A[i][0] * abs(A[i][1] - (N-1-(i-j))))
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + A[i][0] * abs(A[i][1] - j))

for i in range(N):
    ans = max(ans, dp[N][i])

print(ans)


### FIXED CODE ###

import sys
# def input(): return sys.stdin.readline().rstrip()
# input = sys.stdin.readline
input = sys.stdin.buffer.readline

N = int(input())
A = sorted(zip(map(int, (input().split())) ,range(N)), reverse=True)

dp = [[0]*(N+1) for _ in range(N+1)]
ans = 0
for i in range(N):
    for j in range(i+1):
        dp[i+1][j]   = max(dp[i+1][j], dp[i][j] + A[i][0] * abs(A[i][1] - (N-1-(i-j))))
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + A[i][0] * abs(A[i][1] - j))

for i in range(N):
    ans = max(ans, dp[N][i])

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

n,k = map(int,input().split())
P = list(map(int,input().split()))
sum_a = 0
index = 0

for i in range(k):
    sum_a += P[i]
num = sum_a
for j in range(1,n-k+1):
    num += P[j+k-1]
    #print(num)
    num -= P[j-1]
    #print(num)
    if(sum_a<num):
        index = j
        sum_a = num

total = 0.0
for m in range(index,index+k):
    total += sum(list(range(P[m]+1)))/P[m]
print(total)


### FIXED CODE ###

n,k = map(int,input().split())
P = list(map(int,input().split()))
sum_a = 0
index = 0

for i in range(k):
    sum_a += P[i]
num = sum_a
for j in range(1,n-k+1):
    num += P[j+k-1]
    #print(num)
    num -= P[j-1]
    #print(num)
    if(sum_a<num):
        index = j
        sum_a = num

total = 0.0
for m in range(index,index+k):
    total += sum(list(range(P[m]+1)))/P[m]
print(total)
### BUGGY CODE ###

s = input()
if int(s)<2019:
    print(0)
elif len(s)<5:
    print(1 if int(s)%2019==0 else 0)
else:
    n = len(s)
    ans = 0
    for i in range(n-1):
        for j in range(4+i,n):
            _s = s[i:j+1]
            if int(_s)%2019==0:
                ans += 1
    print(ans)

### FIXED CODE ###

from collections import Counter
S = input()[::-1]
MOD = 2019
X = [0]
for i,s in enumerate(S):
    X.append((X[-1]+int(s)*pow(10,i,MOD))%MOD)
C = Counter(X)
print(sum([v*(v-1)//2 for v in C.values()]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7) #再帰回数の上限を変更
from collections import deque
N,M=map(int,input().split())
G=[[]for _ in range(N)]

for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)

dist=[10**5+10 for _ in range(N)]
chk=[0 for _ in range(N)]
dist[0]=0
prev=[-1 for _ in range(N)]


que=deque()
que.append((0,-1))

while(len(que)):
    v,p=que.popleft()
    if p==-1:
        pass
    else:
        val=dist[p]+1
        if val<dist[v]:
            dist[v]=val
            prev[v]=p
    chk[v]=1
    for tmp in G[v]:
        if tmp==p:
            continue
        if chk[tmp]==1:
            continue
        que.append((tmp,v))

print("Yes")
#print(dist)
for i in range(N):
    if i==0:
        continue
    print(prev[i]+1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7) #再帰回数の上限を変更
from collections import deque
N,M=map(int,input().split())
G=[[]for _ in range(N)]

for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)

dist=[-1 for _ in range(N)]
chk=[0 for _ in range(N)]
dist[0]=0
prev=[-1 for _ in range(N)]


que=deque()
que.append((0,-1))

while(len(que)):
    v,p=que.popleft()
    for tmp in G[v]:
        if dist[tmp]!=-1:
            continue
        dist[tmp]=dist[v]+1
        prev[tmp]=v
        que.append((tmp,v))

print("Yes")
#print(dist)
for i in range(N):
    if i==0:
        continue
    print(prev[i]+1)