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

def loc_decide(loc, w, num):
    location = [i for i in range(len(loc)) if loc[i] == num][0]
    #print(location)
    row = location // w
    column = location % w
    return [row, column]

h, w, d = map(int, input().split())
loc = []
for _ in range(h):
    tmp = list(map(int, input().split()))
    for i in range(len(tmp)):
        loc.append(tmp[i])
n = int(input())
for _ in range(n):
    start, end = map(int, input().split())
    dist = 0
    for i in range(start, end+1, d):
        if i == start:
            prev_loc = loc_decide(loc, w, i)
        else:
            next_loc = loc_decide(loc, w, i)
            dist += (abs(next_loc[0]- prev_loc[0]) + abs(next_loc[1] - prev_loc[1]))
            prev_loc = next_loc
    print(dist)

### FIXED CODE ###

h, w, d = map(int, input().split())
d_x = [-1] * (h*w + 1)
d_y = [-1] * (h*w + 1)
for i in range(h):
    tmp = list(map(int, input().split()))
    for j in range(len(tmp)):
        d_x[tmp[j]] = i
        d_y[tmp[j]] = j

dist = [-1] * (h*w + 1) 
for i in range(h*w):
    j = h*w - i
    if h*w - j < d:
        dist[j] = 0
    else:
        dist[j] = dist[j+d] + abs(d_x[j+d] - d_x[j]) + abs(d_y[j+d] - d_y[j])
    
q =  int(input())
for _ in range(q):
    start, end = map(int, input().split())
    print(dist[start]- dist[end])
### BUGGY CODE ###

n,x,m = map(int, input().split())
ans = x
be = x
for i in range(n-1):
    be = be**2
    if be % m == 0:
        break
    else:
        ans += (be%m)
print(ans)


### FIXED CODE ###

n,x,m = map(int, input().split())
be = x % m
ans = be
memo = [[0,0] for i in range(m)]
am = [be]
memo[be-1] = [1,0]  #len-1
for i in range(n-1):
    be = be**2 % m
    if be == 0:
        break
    elif memo[be-1][0] == 1:
        kazu = memo[be-1][1]
        l = len(am) -  kazu
        syou = (n-i-1) // l
        amari = (n-i-1)%l
        sum = 0
        for k in range(kazu, len(am)):
            sum += am[k]
        ans = ans + syou*sum
        if amari > 0:
            for j in range(kazu,kazu + amari):
                ans += am[j]
        break
    else:
        ans += be
        am.append(be)
        memo[be-1][0] = 1
        memo[be-1][1] = len(am) -1
print(ans)
### BUGGY CODE ###

"""
ジャガー「わからん」
先にmax,minそれぞれの和を求める
"""

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def getComb(n, k, MOD):
    if n < k:
        return 0
    if n-k < k:
        k = n-k
    # n!/(n-k)!
    comb = 1
    for x in range(n-k+1, n+1):
        comb = (comb * x) % MOD
    # k!
    d = 1
    for x in range(1, k+1):
        d = (d * x) % MOD
    # n!/((n-k)!*k!)
    comb *= pow(d, MOD-2, MOD)
    return comb % MOD

def main():
    N,K = map(int,input().split())
    A = sorted([int(i) for i in input().split()])
    #print(A)
    
    mod = 10**9+7

    cmb = [0] * (N-K+1)
    for i in range(N-K+1):
        cmb[i] = getComb(i+(K-1),K-1,mod)
    #print(cmb)

    sum_max = 0
    for i in range(K-1,N):
        sum_max = (sum_max + cmb[i-(K-1)] * A[i]) % mod
    #print(sum_max)

    sum_min = 0
    for i in range(N-K,-1,-1):
        sum_min = (sum_min + cmb[(N-K)-i] * A[i]) % mod
    #print(sum_min)

    answer = sum_max - sum_min
    print(answer % mod)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def getComb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p


N,K = map(int,input().split())
A = sorted([int(i) for i in input().split()])

# ref: https://www.planeta.tokyo/entry/5195/
mod = 10**9+7
fact = [1, 1]
factinv = [1, 1] 
inv = [0, 1]
for i in range(2,N+1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

cmb = [0] * (N-K+1)
for i in range(N-K+1):
    cmb[i] = getComb(i+(K-1),K-1,mod)

sum_max = 0
for i in range(K-1,N):
    sum_max = (sum_max + cmb[i-(K-1)] * A[i]) % mod

sum_min = 0
for i in range(N-K,-1,-1):
    sum_min = (sum_min + cmb[(N-K)-i] * A[i]) % mod

answer = sum_max - sum_min
print(answer % mod)
### BUGGY CODE ###

def f(n):
  ans = 0
  while n > 0:
    ans += n % 10
    n // 10
  return ans

n = int(input())
if n % f(n) == 0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

n = input()
ni = int(n)
f = 0
for ns in n:
  f += int(ns)
if ni % f == 0:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

n = int(input())
num_list = list(map(int, input().split()))
num_list.sort()
num_list.reverse()
answer_list = []
max_num = 0
flag = False
for i in range(num_list[0], 0, -1):
    if flag and count < 2:
        break
    else:
        flag = True
        count = 0
        max_num = i
    for j in range(n):
        if num_list[j] / max_num < 1 or num_list[j] % max_num != 0:
            count += 1
            if count > 1:
                break
print(max_num)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
end = sorted(a)[1]

for i in range(end + 1, 0, -1):
    x = 0
    for j in a:
        if j % i != 0:
            x += 1
        if x >= 2:
            break
    if x <= 1:
        print(i)
        break
### BUGGY CODE ###

lenght = int(input())
 
x = list(map(int,input().split()))
first_value = 1
for val in x:
  first_value *= val
if first_value > 1e18:
  print(-1)
else:
  print(first_value)

### FIXED CODE ###

lenght = int(input())
 
x = list(map(int,input().split()))
x.sort(reverse=True)
check = False

if x[-1]==0:
  print(0)
else:
  first_value = 1
  for val in x:
    first_value *= val
    if first_value > 1e18:
      check=True
      break
  if check:
    print(-1)
  else:
  	print(first_value)
### BUGGY CODE ###

x = int(input())

# 最大n個は買う必要がある
n = x // 100

# 最低m個買う必要がある
m = x // 105

ans = 0
# もし割り切れたら、OK
for i in range(100,106):
  if x % i == 0:
    ans = 1
    break

import itertools
shinamono = [100,101,102,103,104,105] * (n)
for i in range(m,n+1):
  if ans == 1:
    break
  a = itertools.combinations(shinamono, i)
  for j in a:
    if sum(j) == x:
      ans = 1
      break

print(ans)


### FIXED CODE ###

x = int(input())

ans = 0
for i in range(1,100001):
  if 100 * i <= x and 105 * i >= x:
    ans = 1
    break

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

from itertools import accumulate
N, K = map(int, input().split())
A = list(map(int, input().split()))
N = len(A)

S = [1]
for i in range(0, N):
 S.append(S[i] * A[i])

count = 0
prev = -1
for i in range(K, len(S)):
  current = S[i]//S[count]
  if prev != -1:
    if current > prev:
      print("Yes")
    else:
      print("No")
  prev = current
  count += 1 



### FIXED CODE ###

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

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

def count1(n):
    p=0
    while n!=0:
        if n%2==1:
            p+=1
        n//=2        
    return p

N=int(input())
X=input()
for i in range(N):
    Ni2=X
    if X[i]=='0':
        Ni2=X[:i]+'1'+X[(i+1):] #文字列は変更できない
    else:
        Ni2=X[:i]+'0'+X[(i+1):]
    Ni=int(Ni2,2)
    ans=0
    #print(Ni)
    while Ni!=0:
        Ni=Ni%count1(Ni)
        ans+=1
    print(ans)

### FIXED CODE ###

N = int(input())
X = input()
popcount_X = X.count('1')
numX = int(X, 2)
a = numX % (popcount_X + 1)
b = numX % (popcount_X - 1) if popcount_X != 1 else 0
for i, x in enumerate(X, 1): #リストのインデクス，要素，第二引数に開始位置
    if x == '1' and popcount_X == 1:
        print(0)
        continue
    ans = 1
    if x == '1':
        temp = (b - pow(2, N - i, popcount_X - 1)) % (popcount_X - 1)
    else:
        temp = (a + pow(2, N - i, popcount_X + 1)) % (popcount_X + 1)
    while temp:
        p = format(temp, 'b').count('1') #2進数，1の個数
        temp %= p
        ans += 1
    print(ans)
### BUGGY CODE ###

N, X, D = map(int, input().split())
M = [0]*N
M[0] = int(input())
P = [0]*N
for i in range(N-1):
    M[i+1], P[i+1] = map(int, input().split())

C = [1]*N
for i in range(N-1, 0, -1):
    p = P[i]-1
    C[p] += C[i]
    M[p] += M[i]
L = [D]*N
L[0] = X

from collections import deque

def solve(N, W, ws, vs, ms):
    V0 = max(vs)
    V = sum(v * min(V0, m) for v, m in zip(vs, ms))

    dp = [W+1]*(V + 1)
    dp[0] = 0
    for i in range(N):
        v = vs[i]; w = ws[i]; m = ms[i]
        c = min(V0, m)
        ms[i] -= c
        for k in range(v):
            que = deque()
            push = que.append
            popf = que.popleft; popb = que.pop

            for j in range((V-k)//v+1):
                a = dp[k + j*v] - j * w
                while que and a <= que[-1][1]:
                    popb()
                push((j, a))

                p, b = que[0]

                dp[k + j*v] = b + j * w
                if que and p <= j-c:
                    popf()

    *I, = range(N)
    I.sort(key=lambda x: ws[x]/vs[x])
    *S, = [(vs[i], ws[i], ms[i]) for i in I]

    def greedy():
        yield 0
        for i in range(V + 1):
            if dp[i] > W:
                continue
            rest = W - dp[i]
            r = i
            for v, w, m in S:
                m = min(m, rest // w)
                r += m * v
                rest -= m * w
            yield r
    return max(greedy())

print(solve(N, X, M, C, L))

### FIXED CODE ###

N, X, D = map(int, input().split())
M = [0]*N
M[0] = int(input())
P = [0]*N
for i in range(N-1):
    M[i+1], P[i+1] = map(int, input().split())

C = [1]*N
for i in range(N-1, 0, -1):
    p = P[i]-1
    C[p] += C[i]
    M[p] += M[i]
L = [D]*N
L[0] = X

from collections import deque

def solve(N, W, ws, vs, ms):
    V0 = max(vs)
    V = sum(v * min(V0, m) for v, m in zip(vs, ms))

    dp = [W+1]*(V + 1)
    dp[0] = 0
    for i in range(N):
        v = vs[i]; w = ws[i]; m = ms[i]
        c = min(V0, m)
        ms[i] -= c
        for k in range(v):
            que = deque()
            push = que.append
            popf = que.popleft; popb = que.pop

            for j in range((V-k)//v+1):
                a = dp[k + j*v] - j * w
                while que and a <= que[-1][1]:
                    popb()
                push((j, a))

                p, b = que[0]

                dp[k + j*v] = b + j * w
                if que and p <= j-c:
                    popf()

    *I, = range(N)
    I.sort(key=lambda x: ws[x]/vs[x])
    *S, = [(vs[i], ws[i], ms[i]) for i in I]

    def greedy():
        yield 0
        for i in range(V + 1):
            if dp[i] > W:
                continue
            rest = W - dp[i]
            r = i
            for v, w, m in S:
                m = min(m, rest // w)
                r += m * v
                rest -= m * w
            yield r
    return max(greedy())

print(solve(N, X, M, C, L))
### BUGGY CODE ###

N = int(input())
#A = [int(a) for a in input().split()]
A = input().split()

ans = 1

for a in range(0,N):
	ans = ans * int(A[a])

#for a in input().split:
#	ans = ans * a


if ans > 10 ** 18:
	ans = -1

print(ans)

### FIXED CODE ###

N = int(input())
#A = [int(a) for a in input().split()]
#A = input().split()
A = list(map(int,input().split()))

ans = 1

if 0 in A:
	print(0)
else:
	for a in range(N):
		ans = ans * A[a]

		if ans > (10 ** 18):
			ans = -1
			break
	print(ans)
### BUGGY CODE ###

MOD=10**9+7
n=int(input())
x=[0 for i in range(60)]
a=list(map(int,input().split()))

for i in range(n):
    k=0
    while a[i]>0:
        if a[i]&1:
            x[k]+=1
        a[i]>>=1
        k+=1
ans=0
for i in range(60):
    ans+=x[i]*(n-x[i])*(2**i)
    ans%=MOD
print(ans)

### FIXED CODE ###

def main():
    MOD=10**9+7
    n=int(input())
    x=[0 for i in range(60)]
    a=list(map(int,input().split()))

    for i in range(n):
        k=0
        while a[i]>0:
            if a[i]&1:
                x[k]+=1
            a[i]>>=1
            k+=1
    ans=0
    b=1
    for i in range(60):
        ans+=x[i]*(n-x[i])*b
        ans%=MOD
        b=(b*2)%MOD
    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

S = input()

cnt = 0
while "BW" in S:
    cnt += S.count("BW")
    S = S.replace("BW", "WB")

print(cnt)


### FIXED CODE ###

S = input()

ans = 0
cnt = 0
for i in range(len(S)):
    if S[i] == "B":
        cnt += 1
    else:
        ans += cnt
print(ans)
### BUGGY CODE ###

n = int(input())
li = []
for i in range(n):
    li.append(int(input()))
m = max(li)
li2 = li.copy()
li2.remove(max(li2))
d = max(li2)
for i in range(n):
    if li[i] == max(li):
        print(d)
    else:
        print(m)

### FIXED CODE ###

n = int(input())
li = []
for i in range(n):
    x = int(input())
    li.append(x)
p = max(li)
r = li.index(p)
li.remove(p)
q = max(li)
for i in range(n):
    if i == r:
        print(q)
    else:
        print(p)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)


n, q = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)

p = [0] * n
for _ in range(q):
    i, x = map(int, input().split())
    p[i-1] += x

parent = [0] * n
res = [0] * n
visited = [False] * n
def dfs(x, n):
    res[x] += n
    visited[x] = True
    for ne in adj[x]:
        if not visited[ne]:
            dfs(ne, n + p[ne])

dfs(0, p[0])
print(' '.join([str(x) for x in res]))



### FIXED CODE ###

import sys

n, q = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append(b)

res = [0] * n
for _ in range(q):
    i, x = map(int, input().split())
    res[i-1] += x

parent = [0] * n
stack = [0]
while len(stack) > 0:
    i = stack.pop()
    for j in adj[i]:
        res[j] += res[i]
        stack.append(j)

print(' '.join([str(x) for x in res]))
### BUGGY CODE ###

import sys
import re
input = sys.stdin.readline

if __name__ == '__main__':
  n=int(input())
  #A=list(map(int,input().strip("\n").split()))
  A=input().strip("\n")
  q=int(input())

  b,c=input().strip("\n").split()
  A=A.replace(b,c).replace(" ","+")
  ans=''
  ans+=str(eval(A))
  ans+="\n"
  for _ in range(1,q-1):
    #b,c=map(int,input().strip("\n").split())
    b,c=input().strip("\n").split()
    A=A.replace(b,c)
    ans+=str(eval(A))
    ans+="\n"
  b,c=input().strip("\n").split()
  A=A.replace(b,c)
  ans+=str(eval(A))
  print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

if __name__ == '__main__':
  n=int(input())
  A_str=input().strip("\n")
  A=A_str.split()
  q=int(input())

  C={}
  for a in A:
    if a in C:
      C[a]+=1
    else:
      C[a]=1
  
  def rep(b,c):
    if c in C:
      C[c]+=C[b]
    else:
      C[c]=C[b] 
    C[b]=0
    #print(b,c,C)

  Ans=[]
  ans=''
  b,c=input().strip("\n").split()
  #tmp=eval(A_str.replace(b,c).replace(" ","+"))
  tmp=0
  hoge=map(int,A)
  for a in hoge:
    if str(a)==b:
      tmp+=int(c)
    else:
      tmp+=a
  #ans+=str(tmp)
  #ans+="\n"
  Ans.append(tmp)
  if b in C:
    rep(b,c)
  for i in range(1,q-1):
    b,c=input().strip("\n").split()
    if b in C:
      tmp+=(int(c)-int(b))*C[b]
      rep(b,c)
    #ans+=str(tmp)+"\n"
    Ans.append(tmp)
  b,c=input().strip("\n").split()
  if b in C:
    tmp+=(int(c)-int(b))*C[b]
  #ans+=str(tmp)
  Ans.append(tmp)
  #print(ans)
  for ans in Ans:
    print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, k = LI()
    g = [[] for i in range(n+1)]
    for i in range(n-1):
        a, b = LI()
        g[a].append(b)
        g[b].append(a)

    s = 1
    Q = [s]
    ans = k
    Qappend = Q.append
    searched = [0] * (n+1)
    searched[s] = 1
    while len(Q) != 0:
        v = Q.pop()
        if v == s:
            cand = k - 1
        else:
            cand = k - 2
        for i in g[v]:
            if searched[i] == 1:
                continue
            searched[i] = 1
            ans *= cand
            cand -= 1
            Qappend(i)
        ans = ans % MOD
    print(ans % MOD)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

import numpy as np
q = list(map(int, input().split()))
w= list(map(int, input().split()))
memo=0
a=0
x=np.array(w)
for i in range(q[0]-q[1]+1):
  k=0
  k=np.sum(x[i:i+q[1]])
  if a<k:
    a=k
    memo=i
print((a+q[1])/2)

### FIXED CODE ###

n,k= list(map(int, input().split()))
j = list(map(int, input().split()))
s=0
sumlist=[0]*(n+1)
anslist=[0]*(n-k+1)
for i in range(n):
    s+=j[i]
    sumlist[i+1]=s
for i in range(len(anslist)):
     z=sumlist[i+k]-sumlist[i]
     anslist[i]=z
ans=max(anslist)
ans+=k
ans=ans/2
print(ans)
### BUGGY CODE ###

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

MOD = 10 ** 9 + 7

pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(a)

flag = False  # 積を正にできるか

if N == K:
    ans = 1
    for a in A:
        ans *= a % MOD
    print(ans % MOD)
    exit()


if len(pos) > 0:
    flag = True
else:
    if K % 2 == 0:
        flag = True

ans = 1
if not flag:
    # 積を正にできないとき
    # 絶対値の小さい方からK個とる
    A = sorted([abs(x) for x in A])
    for a in A[:K]:
        ans *= a % MOD
    ans *= -1
else:
    pos = sorted(pos)
    neg = sorted(neg, reverse=True)
    if K % 2 == 1:
        # Kが奇数の時
        # 一番大きい偶数を1つとる。
        ans *= pos.pop() % MOD

    # pos, neg sort -> 2個ずつペア -> 降順sort -> 上から K//2 個とる
    pairs = []
    while len(pos) >= 2:
        x = pos.pop()
        x *= pos.pop()
        pairs.append(x)
    while len(neg) >= 2:
        x = neg.pop()
        x *= neg.pop()
        pairs.append(x)
    pairs = sorted(pairs, reverse=True)
    for p in pairs[: K // 2]:
        ans *= p % MOD

print(ans % MOD)



### FIXED CODE ###

import sys
import heapq

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


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

    MOD = 10 ** 9 + 7

    pos = []
    neg = []
    for a in A:
        if a >= 0:
            pos.append(a)
        else:
            neg.append(a)

    flag = False  # 積を正にできるか

    if N == K:
        ans = 1
        for a in A:
            ans *= a
            ans %= MOD
        print(ans % MOD)
        exit()

    if len(pos) > 0:
        flag = True
    else:
        if K % 2 == 0:
            flag = True

    ans = 1
    if not flag:
        # 積を正にできないとき
        # 絶対値の小さい方からK個とる
        h = [abs(x) for x in A]
        heapq.heapify(h)

        for i in range(K):
            ans *= heapq.heappop(h)
            ans %= MOD
        ans *= -1
    else:
        hpos = [-x for x in pos]
        heapq.heapify(hpos)
        hneg = neg[:]
        heapq.heapify(hneg)
        if K % 2 == 1:
            # Kが奇数の時
            # 一番大きい偶数を1つとる。
            ans *= -heapq.heappop(hpos)
            ans %= MOD

        # pos, neg sort -> 2個ずつペア -> 降順sort -> 上から K//2 個とる
        pairs = []
        while len(hpos) >= 2:
            x = -heapq.heappop(hpos)
            x *= -heapq.heappop(hpos)
            heapq.heappush(pairs, -x)
        while len(hneg) >= 2:
            x = heapq.heappop(hneg)
            x *= heapq.heappop(hneg)
            heapq.heappush(pairs, -x)
        if len(pairs):
            for i in range(K // 2):
                ans *= -heapq.heappop(pairs)
                ans %= MOD

    print(ans % MOD)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

from bisect import bisect_left
s=list(input())
count=0
while True:
  flag=1
  i=bisect_left(s,"B")
  while i+1 <len(s):
    if s[i]=="B" and s[i+1]=="W":
      s[i]="W"
      s[i+1]="B"
      count+=1
      i+=1
      flag=0
    else:
      i+=1
      continue
  if flag==1:
    print(count)
    exit()

### FIXED CODE ###

s=list(input())
count=0
# print('lens',len(s))
indexes = [i for i, x in enumerate(s) if x == "B"]
ideal=sorted([len(s)-i-1 for i in range(len(indexes))])
# print(indexes)
# print(ideal)
for i in range(len(indexes)):
  count+=ideal[i]-indexes[i]

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

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    inf = 10**17
    #mod = 10**9 + 7

    N = int(input())
    a = list(map(int, input().split()))
    b = [0] + list(accumulate(a))
    dp = [[inf]*N for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0
    for j in range(1, N):
        for l in range(0, N-j):
            r = l + j
            temp = b[r+1] - b[l]
            #区間の境界
            for k in range(l, r):
                dp[l][r] = min(dp[l][r], dp[l][k]+dp[k+1][r]+temp)
            
    print(dp[0][-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    inf = 10**17
    #mod = 10**9 + 7

    N = int(input())
    a = list(map(int, input().split()))
    b = [0] + list(accumulate(a))
    dp = [[inf]*N for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0
    for j in range(1, N):
        for l in range(0, N-j):
            r = l + j
            temp = b[r+1] - b[l]
            #区間の境界
            for k in range(l, r):
                dp[l][r] = min(dp[l][r], dp[l][k]+dp[k+1][r]+temp)
            
    print(dp[0][-1])

if __name__ == '__main__':
    main()