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

import math

N=int(input())
sqN = int(math.sqrt(N))+1

sq=list()
for i in range(1,200):
    sq.append(i*i)

def isSquare(n):
    if n in sq:
        return True
    else:
        return False

ans=list()
for i in range(1,min(N+1,6)):
    ans.append(0)

if N>5:
    for m in range(6,N+1):
        cnt = 0
        for x in range(1,sqN):
            for y in range(x,sqN):
                if x*x+y*y+x*y+x+y > m:
                    break

                b = x+y
                D = -3*(x*x+y*y)-2*x*y+4*m

                # print(m,x,y,D,isSquare(D))
                if D > 0 and isSquare(D):
                    sqD=sq.index(D)+1
                    if (sqD-b) > 0 and (sqD-b) % 2 == 0:
                        # z= (sqD-b)//2
                        # print(x,y,z)
                        # print(x*x+y*y+z*z+x*y+y*z-m)
                        if x != y:
                            cnt+=2
                        else:
                            cnt+=1
                if D < 0:
                    break
        ans.append(cnt)

for a in ans:
    print(a)
                         
                    


### FIXED CODE ###

N=int(input())

cnts=[0 for i in range(N+1)]

for x in range(1,100):
    x2=x*x
    for y in range(x,100):
        y2=y*y
        xy=x*y
        if x2+y*y+x*y+x+y > N:
            break

        for z in range(y,100):
            z2 = z*z
            M = x2+y2+z2+xy+y*z+z*x
            if M > N:
                break
            if x!=y:
                if y!=z:
                    cnts[M]+=6
                else:
                    cnts[M]+=3
            else:
                if y!=z:
                    cnts[M]+=3
                else:
                    cnts[M]+=1

for a in cnts[1:N+1]:
    print(a)
### BUGGY CODE ###

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

ans = 100000000

for i in range(N):
    A = S[0:i]
    B = S[i+1:]
    X = A.count('W')
    Y = B.count('E')
    ans = min(X + Y,ans)
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
e = s.count("E")
w = s.count("W")
cnt1 = 0
cnt2 = 0
ans = 10e9
for i in s:
    if i=="E":
        cnt1 += 1
        ans = min(ans,cnt2+e-cnt1)
    else:
        ans = min(ans,cnt2+e-cnt1)
        cnt2 += 1
print(ans)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
a, b, n = map(int, input().split())
max_score = 0
for x in range(1, n + 1):
    score = int(a * x / b) - a * (x // b)
    if max_score < score:
        max_score = score
print(max_score)

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
a, b, n = map(int, input().split())
max_score = 0
if n < b:
    max_score = int(a * n / b) - a * (n // b)
elif n == b:
    max_score = max(int(a * n / b) - a * (n // b), int(a * (n-1) / b) - a * ((n-1) // b))
elif a <= b:
    max_score = a - 1
elif a >= b:
    max_score = int(a * (b-1) / b) - a * ((b-1) // b)
else:
    for x in range(1, n + 1):
        score = int(a * x / b) - a * (x // b)
        if max_score < score:
            max_score = score
print(max_score)
### BUGGY CODE ###

#解説解答
n,a = map(int,input().split())
x = list(map(int,input().split()))
dp0 = [[0 for s in range(n*a+1)] for k in range(n+1)]
dp0[0][0] = 1
dp = [dp0]
for j in range(n):
  now = [[] for k in range(n+1)]
  for k in range(n+1):
    for s in range(n*a+1):
      if s-x[j] >= 0 and k >= 1:
        now[k].append( dp[j][k][s] + dp[j][k-1][max(0,s-x[j])] )
      else:
        now[k].append( dp[j][k][s] )
  dp.append(now)
now = dp[n]
ans = 0
for k in range(1,n+1):
  ans += now[k][k*a]
print(ans)

### FIXED CODE ###

#解説解答
n,a = map(int,input().split())
x = list(map(int,input().split()))
dp0 = [[0 for s in range(n*a+1)] for k in range(n+1)]
dp0[0][0] = 1
dp = dp0
for j in range(n):
  now = []
  for k in range(n+1):
    add = []
    for s in range(n*a+1):
      t = s-x[j]
      if t >= 0 and k >= 1:
        add.append( dp[k][s] + dp[k-1][t] )
      else:
        add.append( dp[k][s] )
    now.append(add)
  dp = now
ans = 0
for k in range(1,n+1):
  ans += dp[k][k*a]
print(ans)
### BUGGY CODE ###

from bisect import bisect_left
A, B, Q = map(int, input().split())
BIG = 10**10 + 1
S = [-BIG] + sorted([int(input()) for _ in range(A)]) + [BIG*2]
T = [-BIG] + sorted([int(input()) for _ in range(B)]) + [BIG*2]
for _ in range(Q):
  x = int(input())
  shrine_b = bisect_left(S, x)
  shrine_l = S[shrine_b-1]
  shrine_r = S[shrine_b]
  temple_b = bisect_left(T, x)
  temple_l = T[temple_b-1]
  temple_r = T[temple_b]
  print(min(
    x-shrine_l if shrine_l < temple_l else x-temple_l,
    shrine_r-x if shrine_r > temple_r else temple_r-x,
    (x-shrine_l) * 2 + temple_r-x,
    x-shrine_l + (temple_r-x) * 2,
    (shrine_r-x) * 2 + x-temple_l,
    shrine_r-x + (x-temple_l) * 2
  ))

### FIXED CODE ###

from bisect import bisect_right
A, B, Q = map(int, input().split())
BIG = 10**10 + 1
S = [-BIG] + [int(input()) for _ in range(A)] + [BIG*2]
T = [-BIG] + [int(input()) for _ in range(B)] + [BIG*2]
for _ in range(Q):
  x = int(input())
  shrine_b = bisect_right(S, x)
  dsl = x-S[shrine_b-1]
  dsr = S[shrine_b]-x
  temple_b = bisect_right(T, x)
  dtl = x-T[temple_b-1]
  dtr = T[temple_b]-x

  print(min(
    dsl if dsl > dtl else dtl,
    dsr if dsr > dtr else dtr,
    dsl * 2 + dtr,
    dsl + dtr * 2,
    dsr * 2 + dtl,
    dsr + dtl * 2
  ))
### BUGGY CODE ###

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

w = [0] * (N + 1)
v = [0] * (N + 1)

for i in range(1, N + 1):
    w[i], v[i] = map(int, input().split())
    
MAX_W = 1000000
dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    for weight in range(1, W + 1):
        if weight - w[i] >= 0:#入れられる可能性があるかどうか
            dp[i][weight] = max(dp[i][weight], dp[i - 1][weight-w[i]] + v[i])#ある場合は、直前まででLimitがweight-w[i]の最大値と比較
#dp[i][weight] = i-1番目までの品から重さがweight以下になるように選んだ時の価値の最大値
        dp[i][weight] = max(dp[i-1][weight], dp[i][weight])

print(dp[N][W])

### FIXED CODE ###

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

w = [0] * (N + 1)
v = [0] * (N + 1)

for i in range(1, N + 1):
    w[i], v[i] = map(int, input().split())
    
MAX_W = 1000000
dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    for weight in range(1, W + 1):
        if weight - w[i] >= 0:#入れられる可能性があるかどうか
            dp[i][weight] = max(dp[i][weight], dp[i - 1][weight-w[i]] + v[i])#ある場合は、直前まででLimitがweight-w[i]の最大値と比較
#dp[i][weight] = i-1番目までの品から重さがweight以下になるように選んだ時の価値の最大値
        dp[i][weight] = max(dp[i-1][weight], dp[i][weight])

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

import math
x,y = map(int,input().split())
sum_xy = x+y

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

if sum_xy%3!=0:
    print(0)
else:
    ab_sum = sum_xy//3
    a = x-ab_sum
    b = y-ab_sum
    print(cmb(ab_sum,a,inf))

### FIXED CODE ###

x, y = map(int, input().split())
if (x+y)%3 != 0:
    print(0)
    exit()

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
 
mod = 10**9+7
N = 10**6
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
 
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
 
 
a = (2*x-y)//3
b = (2*y-x)//3
n = a+b
r = a
res = cmb(n,r,mod)
print(res)
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[10*5]*n
dp[0]=0
for i in range(1,n):
    dp[i]=min(dp[j]+abs(h[j]-h[i]) for j in range(max(0,i-k),i))
print(dp[-1])


### FIXED CODE ###

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

import math
import queue

def readInt():
	return int(input())

def readInts():
	return list(map(int, input().split()))

def readChars():
	return input().split()

s = input()

ai = [0]*len(s)
si = [0]*len(s)

p = 2019

for i in range(len(s)):
	ai[i] = (int(s[-1*i-1])*pow(10,i))%p
for i in range(len(ai)):
	si[i] = sum(ai[:i+1])%p
	#print(ai[:i+1],1)
countarr = [0]*2019
for i in si:
	countarr[i]+=1

res = countarr[0]
for i in range(p):
	c = countarr[i]
	res += c*(c-1)//2

print(res)

### FIXED CODE ###

import math

def readInt():
	return int(input())

def readInts():
	return list(map(int, input().split()))

def readChars():
	return input().split()

s = reversed(input())

ai = 0
si = 0

p = 2019
countarr = [0]*2019

for i, j in enumerate(s):
	ai = (int(j)*pow(10,i,p))%p
	si = (si+ai)%p
	countarr[si]+=1

res = countarr[0]
for i in range(p):
	c = countarr[i]
	res += c*(c-1)//2

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

from copy import copy
import random
random.seed(0)
import math
import sys
input = sys.stdin.readline
D = int(input())
c = list(map(int,input().split()))
s = [list(map(int,input().split())) for _ in range(D)]
last = [0]*26
ans = [0]*D
score = 0
for i in range(D):
    ps = [0]*26
    for j in range(26):
        pl = copy(last)
        pl[j] = i+1
        ps[j] += s[i][j]
        for k in range(26):
            ps[j] -= c[k]*(i+1-pl[k])
    idx = ps.index(max(ps))
    last[idx] = i+1
    ans[i] = idx+1
    score += max(ps)
for k in range(1,30001):
    na = copy(ans)
    x = random.randint(1,365)
    y = random.randint(1,26)
    na[x-1] = y
    last = [0]*26
    ns = 0
    for i in range(D):
        last[na[i]-1] = i+1
        ns += s[i][na[i]-1]
        for j in range(26):
            ns -= c[j]*(i+1-last[j])
    if k%100 == 1:
        T = 300-(298*k/30000)
    p = pow(math.e,-abs(ns-score)/T)
    if ns > score or random.random() < p:
        ans = na
        score = ns
random.seed(1)
for k in range(1,5001):
    na = copy(ans)
    x = random.randint(1,365)
    y = random.randint(1,365)
    na[x-1],na[y-1] = na[y-1],na[x-1]
    last = [0]*26
    ns = 0
    for i in range(D):
        last[na[i]-1] = i+1
        ns += s[i][na[i]-1]
        for j in range(26):
            ns -= c[j]*(i+1-last[j])
    if ns > score:
        ans = na
        score = ns
for a in ans:
    print(a)

### FIXED CODE ###

import random
for i in range(365):
  print(random.randint(1,26))
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# Created: Jul, 14, 2020 09:41:55 by Nobody
# $Author$
# $Date$
# $URL$
__giturl__ = "$URL$"


from collections import defaultdict
from sys import stdin
input = stdin.readline


def main():
  N, Q = list(map(int, input().split()))
  G = [[] for _ in range(N+1)]
  for _ in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
  PX = defaultdict(int)

  for _ in range(Q):
    p, x = map(int, input().split())
    PX[p] += x

  ans = [0]*(N+1)
  S = [1]
  is_visited = set()
  temp = PX[1]

  while len(S):
    now = S[-1]
    is_visited.add(now)
    for next_ in G[now]:
      if next_ not in is_visited:
        S.append(next_)
        temp += PX[next_]
        break
    else:
      S.pop()
      ans[now] = temp
      temp -= PX[now]

  print(*ans[1:], sep=' ')


if(__name__ == '__main__'):
  main()


### FIXED CODE ###

import sys
from collections import defaultdict
from collections import deque
from sys import stdin
sys.setrecursionlimit(10**7)
input = stdin.readline


def main():
  # input
  N, Q = list(map(int, input().split()))

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

  PX = defaultdict(int)
  for _ in range(Q):
    p, x = map(int, input().split())
    PX[p] += x

  # solve
  ans = [0]*(N+1)
  visited = set()
  # temp = PX[1]
  # S = [1] # Stack
  # S = deque([1])

  # while len(S):
  #   now = S[-1]
  #   visited.add(now)

  #   for next_ in G[now]:
  #     if next_ not in visited:
  #       S.append(next_)
  #       temp += PX[next_]
  #       break
  #   else:
  #     S.pop()
  #     ans[now] = temp
  #     temp -= PX[now]

  def dfs(now, sum_):
    visited.add(now)
    for next_ in G[now]:
      if next_ not in visited:
        sum_ += PX[next_]
        sum_ = dfs(next_, sum_)

    ans[now] = sum_
    sum_ -= PX[now]
    return sum_

  dfs(1, PX[1])

  print(*ans[1:], sep=' ')


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

N = int(input())
A =[]

hantei = True
tmp = input().split()

for i in range(N):
  tmp_int = int(tmp[i])
  if tmp_int in A:
    hantei = False
  A.append(tmp_int)
  

if(hantei == True):
  print("YES")
else:
  print("NO")

### FIXED CODE ###

N = int(input())
A = []

tmp = input().split()

for i in range(N):
  A.append(int(tmp[i]))
    
A.sort()

hantei = True

for i in range(N-1):
  if A[i] == A[i+1]:
    hantei = False
    
if hantei == True:
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

N = int(input())
S = input()
count = 0
for i in range(1000):
    pas = format(i).zfill(3)
    a, b = 0, 0
    for j in range(N-2):
        if S[j] == pas[0]:
            a = j
            for k in range(a+1, N-1):
                if S[k] == pas[1]:
                    b = k
                    for l in range(b+1, N):
                        if S[l] == pas[2]:
                            count += 1
                            break
                    break
            break
print(count)


### FIXED CODE ###

N = int(input())
S = input()
count = 0
for i in range(1000):
    pas = format(i).zfill(3)
    a = S[:-2].find(pas[0])
    if a >= 0:
        b = S[a+1:-1].find(pas[1])
        if b >= 0:
            if pas[2] in S[a+b+2:]:
                count += 1
print(count)
### BUGGY CODE ###

def lucas(n):
    if n>=2:
        return lucas(n-1)+lucas(n-2)
    if n==0:
        return 2
    if n==1:
        return 1
print(lucas(int(input())))

### FIXED CODE ###

def lucas(n):
    global nlist
    if n==0:
        return 2
    if n==1:
        return 1
    if nlist[n]!=0:
        return nlist[n]
    else:
        nlist[n]=lucas(n-1)+lucas(n-2)
        return lucas(n-1)+lucas(n-2)
    
nlist=[0 for a in range(100)]
print(lucas(int(input())))
### BUGGY CODE ###

import sys
_ = int(sys.stdin.readline().strip())                 
xs = [int(x) for x in sys.stdin.readline().split(" ")]
r = 1                                                 
for x in xs:                                          
    r *= x                                            
if r > 10 ** 18:                                      
    print("-1")                                       
else:                                                 
    print(r)                                          

### FIXED CODE ###

import sys
def calc():                                             
    _ = int(sys.stdin.readline())                       
    xs = [int(x) for x in sys.stdin.readline().split(" ")]
    for x in xs:                                          
        if x == 0:                                        
            return 0                                      
    r = 1                                                 
    m = 10 ** 18                                          
    for x in xs:                                          
        r *= x                                            
        if r > m:                                         
            return -1                                     
    return r                                              
                                                          
print(calc())
### BUGGY CODE ###

# import math
# import statistics
# import itertools
# a=int(input())
# b=input()
# c=[]
# for i in a:
#     c.append(int(i))
N,K= map(int,input().split())
# f = list(map(int,input().split()))
# g = [int(input()) for _ in range(N)]
# h = []
# for i in range(a):
#     h.append(list(map(int,input().split())))
# a = [[0] for _ in range(H)]#nizigen
mi=N
count=0
while True:
    if N%K==0:
        print(0)
        exit()
    N=abs(N-K)
    if N<=mi:
        mi=min(mi,N)
        count+=1
    else :
        print(mi)
        exit()




### FIXED CODE ###

# import math
# import statistics
# import itertools
# a=int(input())
# b=input()
# c=[]
# for i in a:
#     c.append(int(i))
N,K= map(int,input().split())
# f = list(map(int,input().split()))
# g = [int(input()) for _ in range(N)]
# h = []
# for i in range(a):
#     h.append(list(map(int,input().split())))
# a = [[0] for _ in range(H)]#nizigen

if N%K==0:
    print(0)
else:
    et=N//K
    a1=et*K
    a2=(et+1)*K
    mi = min(abs(a1-N),abs(a2-N))
    print(mi)
### BUGGY CODE ###

import sys
n,y=map(int,input().split())
for i in range(n+1):
  for j in range(n+1):
    if (y-10000*i-5000*j)%1000==0 and (y-10000*i-5000*j)//1000>=0 and i+j+(y-10000*i-5000*j)//1000==n:
      print(i,j,n-i-j)
      sys.exit()
print(-1,-1,-1)

### FIXED CODE ###

n,y=map(int,input().split())
x=0
for i in range(n+1):
  if x==1:
    break
  for j in range(n-i+1):
    if y==i*10000+j*5000+(n-i-j)*1000:
      print(i,j,n-i-j)
      x=1
      break
if x==0:print(-1,-1,-1)
### BUGGY CODE ###

n = int(input())
S = input()
left = []
right = []
cl = 0
cr = 0
for i in range(n):
  left = left + [cl]
  if S[i] == "#":
    cl += 1
  right = [cr] + right
  if S[n - 1 -i] == ".":
    cr += 1
min = S.count("#")
for i in range(n):
  if S[i] == "#":
    p = left[i] + right[i]
    if p < min:
      min = p
print(min)

### FIXED CODE ###

n = int(input())
S = input()
left = []
right = []
cl = 0
cr = 0
for i in range(n):
  left += [cl]
  if S[i] == "#":
    cl += 1
  right += [cr]
  if S[n - 1 -i] == ".":
    cr += 1
min = cl
for i in range(n):
  if S[i] == "#":
    p = left[i] + right[n - 1 -i]
    if p < min:
      min = p
print(min)
### BUGGY CODE ###

import math
import collections

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
li = list(map(int,input().split()))
c = collections.Counter(li)
c = list(sorted(c.items()))
ans = [0]*n
x = 0 #全てのボールから、できる組合せの総数

for i in c:
    a = i[0]
    b = i[1]
    if b > 2:
        x += combinations_count(b, 2)
    elif b == 2:
        x += 1

for i in c:
    a = i[0]
    b = i[1]
    if b > 2:
        y = x - combinations_count(b, 2) + combinations_count(b-1, 2)
    elif b == 2:
        y = x - 1
    else:
        y = x
    ans[a-1] = y

for i in li:
    print(ans[i-1])

### FIXED CODE ###

import collections

def combinations_count(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

n = int(input())
li = list(map(int,input().split()))
c = collections.Counter(li)
ans = [0]*n
x = 0 #全てのボールから、できる組合せの総数

if len(c) == 1:
    ans = [combinations_count(n-1, 2)]*n
    print(*ans)
    exit()

for i in c.items():
    a = i[0]
    b = i[1]
    if b > 2:
        x += combinations_count(b, 2)
    elif b == 2:
        x += 1

for i in c.items():
    a = i[0]
    b = i[1]
    if b > 2:
        y = x - combinations_count(b, 2) + combinations_count(b-1, 2)
    elif b == 2:
        y = x - 1
    else:
        y = x
    ans[a-1] = y

for i in li:
    print(ans[i-1])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
c=0
for i in range(n):
    for j in range(i+1,n+1):
        if sum(a[i:j])==0:
            c+=1
print(c)

### FIXED CODE ###


from collections import Counter
n=int(input())
a=list(map(int,input().split()))
s=[0]
ans=0
for i in range(n):
    s.append(s[-1]+a[i])  #sの最後とa[i]を足していく
c=Counter(s)    #Counter({4: 2, 2: 2, 1: 1, 0: 1})
for n in dict(c).values():    #{1: 1, 4: 2, 0: 1, 2: 2}のvalueを順に取り出す
    ans+=n*(n-1)//2     #nC2を計算する
print(ans)


'''
from collections import Counter
N = int(input())
A = [int(i) for i in input().split()]
l = [0]
ans = 0
for a in A:
    l.append(l[-1]+a)
c = Counter(l)
print(l)
for n in dict(c).values():
    ans += n*(n-1)//2
print(ans)
'''
### BUGGY CODE ###

n, a, b = map(int, input().split())
total = 0
out = 0
if a == 0:
    pass
else:
    while True:
        total += a
        out += a
        if total >= n:
            out -= (total - n)
            break
        total += b
        if total >= n:
            break
print(out)

### FIXED CODE ###

n, a, b = map(int, input().split())
q = n // (a + b)
mod = n % (a + b)
if mod > a:
    remain = a
else:
    remain = mod
    
print(q * a + remain)
### BUGGY CODE ###

import decimal

def volume(h, w, v):
    return h * w * v

L = decimal.Decimal(input())

max_volume = 0
max_list = []
i = decimal.Decimal(L/3) - 1
if i < 0:
    i = decimal.Decimal(0.01)

while i < L/3+1:
    j = decimal.Decimal(L/3) - 1
    if j < 0:
        j = decimal.Decimal(0.01)
    while j < L/3 + 1:
        k = decimal.Decimal(L - i - j)
        v = volume(i, j, k)
        if max_volume < v:
            max_volume = v
            max_list = [i, j, k]
        j += decimal.Decimal(0.01)
    i += decimal.Decimal(0.01)

print(max_volume)

### FIXED CODE ###

import decimal

def volume(h, w, v):
    return h * w * v

L = decimal.Decimal(input())

i = decimal.Decimal(L/3)
j = decimal.Decimal(L/3)
k = decimal.Decimal(L/3)
max_volume = volume(i, j, k)
while k <= decimal.Decimal(L/3) + 1:
    if i + j + k > L:
        k += decimal.Decimal(0.01)
        continue
    v = volume(i, j, k)
    max_volume = max(max_volume, v)
    k += decimal.Decimal(0.01)

print(max_volume)
### BUGGY CODE ###

while 1:
	try:
		stack = []
		for s in map(str, raw_input().split()):
			if s == "-":
				stack.append(stack.pop(-2) + stack.pop())
			elif s == "+":
				stack.append(stack.pop(-2) - stack.pop())
			elif s == "/":
				stack.append(stack.pop(-2) * stack.pop())
			elif s == "*":
				stack.append(stack.pop(-2) / stack.pop())
			else:
				stack.append(float(s))
	
		print stack[0]
	except:
		pass

### FIXED CODE ###

while 1:
	try:
		stack = []
		for s in raw_input().split():
			if s == "-":
				stack.append(stack.pop(-2) - stack.pop())
			elif s == "+":
				stack.append(stack.pop(-2) + stack.pop())
			elif s == "/":
				stack.append(stack.pop(-2) / stack.pop())
			elif s == "*":
				stack.append(stack.pop(-2) * stack.pop())
			else:
				stack.append(float(s))
	
		print "%.6f" % (stack[0])
	except:
		break
### BUGGY CODE ###

n = int(input())
s = list(map(int,input().split()))
dp = [[0 for _ in range(n)] for _ in range(n)]
psum = [0 for _ in range(n+1)]
sm = 0
for i in range(n):
    sm +=s[i]
    psum[i+1]=sm
def findMin(left,right):
    dp[left][right]=dp[left][left]+dp[left+1][right]+psum[right+1]-psum[left]
    for i in range(left+1,right):
        dp[left][right] = min(dp[left][right],dp[left][i]+dp[i+1][right]+psum[right+1]-psum[left])
for length in range(2,n+1):
    for l in range(n-length+1):
        r = l+length-1
        findMin(l,r)

print(dp[0][n-1])

### FIXED CODE ###

n = int(input())
s = list(map(int,input().split()))
dp = [[0 for _ in range(n)] for _ in range(n)]
psum = [0 for _ in range(n+1)]
sm = 0
for i in range(n):
    sm +=s[i]
    psum[i+1]=sm
def findMin(left,right):
    dp[left][right]=dp[left][left]+dp[left+1][right]+psum[right+1]-psum[left]
    for i in range(left+1,right):
        dp[left][right] = min(dp[left][right],dp[left][i]+dp[i+1][right]+psum[right+1]-psum[left])
for length in range(2,n+1):
    for l in range(n-length+1):
        r = l+length-1
        findMin(l,r)

print(dp[0][n-1])