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

N = int(input())
W = list(map(int, input().split()))
V = []
for T in range(N-1):
  A = 0
  B = 0
  for i in range(N):
    while i <= T:
      A = A + W[i]
    else:
      B = B + W[i]
    V.append(abs(A-B))
  
V = min(str(V[T]))


### FIXED CODE ###

N = int(input())
W = list(map(int, input().split()))
V = []
for i in range(N):
    A = sum(W[0:i])
    B = sum(W[i:N])
    V.append(abs(A-B))
print(min(V))
### BUGGY CODE ###

A, B, N = map(int, input().split())
ans = 0
for i in range(N+1):
    x = (A*i)//B - A*(i//B)
    ans = max(ans, x)
print(ans)

### FIXED CODE ###


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

if N >= B:
    print((A*(B-1))//B)
else:
    print((A*N)//B - A*(N//B))
### BUGGY CODE ###

n=int(input())
table=[0]*60
for i,v  in enumerate(map(int,input().split())):
    for j in range(60):
        table[j]+=v%2
        v//=2
        if v==0:break
ans=0
mod=10**9+7
a=1
n%=mod
for o in table:
    z=(n-o)%mod
    o%=mod
    ans=(ans+o*z*a)%mod
    a=a*2%mod
print(ans)

### FIXED CODE ###

n=int(input())
l=[int(c) for c in input().split()]
ans=0
mod=10**9+7
for i in range(60):
  s=sum(a>>i&1 for a in l)
  ans+=s*(n-s)<<i%mod
  ans%=mod
print(ans)
### BUGGY CODE ###

import math

a, b, c, d, e, f = map(int, input().split())

highest = 0
sugarwater = 0
maxsugar = 0
amax = math.ceil(f / (100 * a))
bmax = math.ceil(f / (100 * b))
cmax = math.ceil(30 * e / c)
dmax = math.ceil(30 * e / d)
for aa in range(amax):
    for bb in range(bmax):
        water = 100 * (aa * a + bb * b)
        if water == 0 or water > f:
            continue
        for cc in range(cmax):
            for dd in range(dmax):
                sugar = cc * c + dd * d
                if sugar / (water / 100) > e or water + sugar > f:
                    continue
                density = 100 * sugar / (water + sugar)
                if density >= highest:
                    highest = density
                    sugarwater = sugar + water
                    maxsugar = sugar
print(sugarwater, maxsugar)


### FIXED CODE ###

import math

a, b, c, d, e, f = map(int, input().split())

highest = 0
sugarwater = 0
maxsugar = 0
amax = math.ceil(f / (100 * a))
bmax = math.ceil(f / (100 * b))
cmax = math.ceil(30 * e / c)
dmax = math.ceil(30 * e / d)
for aa in range(amax):
    for bb in range(bmax):
        water = 100 * (aa * a + bb * b)
        if water == 0 or water > f:
            continue
        for cc in range(cmax):
            for dd in range(dmax):
                sugar = cc * c + dd * d
                if sugar / (water / 100) > e or water + sugar > f:
                    continue
                density = 100 * sugar / (water + sugar)
                if density >= highest:
                    highest = density
                    sugarwater = sugar + water
                    maxsugar = sugar
print(sugarwater, maxsugar)
### BUGGY CODE ###

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


maxnum=0
index=0
num=0
for i in range(len(P)):
    num+=P[i]



    if maxnum<num:
        maxnum=num
        index=i




    if i>=K-1:
        num-=P[i-(K-1)]


List=[]
for i in range(K):
    x1=P[index-i]
    sumx1=0
    for j in range(1,x1+1):
        sumx1+=j

    sumx1=sumx1/x1
    List.append(sumx1)


print(sum(List))


### FIXED CODE ###

import math
N,K = map(int,input().split())
P=list(map(int,input().split()))


maxnum=0
index=0
num=0
for i in range(len(P)):
    num+=P[i]
    if maxnum<num:
        maxnum=num
        index=i




    if i>=K-1:
        num-=P[i-(K-1)]


List=[]
for i in range(K):
    x1=P[index-i]

    sumx1=(1+x1)/2
    List.append(sumx1)


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

# cook your dish here
import bisect
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int,input().split()))
a.sort()
 
 
c = [None]*n #使ったら1
 
res = 0
 
for i in range(n-1,-1,-1):
    if c[i] == None:
        b = 1
        while b <= a[i]:
            b = b*2
        w1 = bisect.bisect_left(a,b-a[i])
        w2 = bisect.bisect_right(a,b-a[i])
        if w2 >w1:
            for p in range(w1,w2):
                if c[p] == None and i != p:
                    res += 1
                    c[p] = 1
                    c[i] = 1
                    break
                
 
print(res)

### FIXED CODE ###

import bisect
 
N = int(input())
A = [int(a) for a in input().split()]
A = sorted(A)
 
c = 0
for i in range(N - 1 , -1, -1):
    if A[i] == int(A[i]):
        b = 1
        while b <= A[i]:
            b <<= 1
 
        j = bisect.bisect_left(A, b - A[i])
        if i > j:
            if b - A[i] == A[j]:
                c += 1
                A[j] = A[j] - 0.5
                A[i] = A[i] + 0.5
print(c)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
H,W=map(int,input().split())


def dfs(h,w):
    que=[]
    if h>0:
        if A[h-1][w]!="#":
            que.append([h-1,w])
    if w>0:
        if A[h][w-1]!="#":
            que.append([h,w-1])
    if h<H-1:
        if A[h+1][w]!="#":
            que.append([h+1,w])
    if w<W-1:
        if A[h][w+1]!="#":
            que.append([h,w+1])
    
    return que


A=[]
for _ in range(H):
    A.append(list(input()))

#print(A)

ans=0
while True:
    lis=[]
    for h in range(H):
        for w in range(W):
            if A[h][w]=="#":
                lis+=dfs(h,w)
    if lis:
        for item in lis:
            A[item[0]][item[1]]="#"
    else:
        break
    ans+=1
    
print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!
H,W=map(int,input().split())


def dfs(h,w):
    A[h][w]="#"
    que=[]
    if h>0:
        if A[h-1][w]!="#":
            que.append([h-1,w])
            A[h-1][w]="#"
    if w>0:
        if A[h][w-1]!="#":
            que.append([h,w-1])
            A[h][w-1]="#"
    if h<H-1:
        if A[h+1][w]!="#":
            que.append([h+1,w])
            A[h+1][w]="#"
    if w<W-1:
        if A[h][w+1]!="#":
            que.append([h,w+1])
            A[h][w+1]="#"
    
    return que


A=[]
for _ in range(H):
    A.append(list(input()))

#print(A)

ans=0
lis=[]
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            lis.append([h,w])
while True:
    pre=[]
    if lis:
        N=len(lis)
        lis=lis[::-1]
        for i in range(N):
            item=lis.pop(-1)
            pre+=dfs(item[0],item[1])
        lis=pre
    if len(lis)==0:
        break
    ans+=1
    #print(lis)
    #print(A)
    
print(ans)
### BUGGY CODE ###

from collections import deque

revFlag = False
s = deque(input())
q = int(input())

for i in range(q):
    a,b,c, *_ = input().split() + [None, None]
    
    if(a == '1'):
        revFlag = not revFlag
    else:
        if(revFlag):
            s.reverse()
            revFlag = False
        
        if(b == '1'):
            s.appendleft(c)
        else:
            s.append(c)

if(revFlag):
    s.reverse()
    
print(*s, sep='')


### FIXED CODE ###

from collections import deque

revFlag = False

s = deque(input())
q = int(input())

for i in range(q):
    a,b,c, *_ = input().split() + [None, None]
    
    if(a == '1'):
        revFlag = not revFlag
        
    else:
        b = int(b)
        if(revFlag):
            b = (int(b)%2)+1
        
        if(b == 1):
            s.appendleft(c)
        else:
            s.append(c)
            
    #print(_,*s, sep="")

if(revFlag):
    s.reverse()
    
print(*s, sep='')
### BUGGY CODE ###

import sys
import copy
sys.setrecursionlimit(10**7)
n,m,k=map(int,input().split())
friend=[[]for i in range(n)]
block=[[]for i in range(n)]
G=[[]for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
for i in range(k):
    c,d=map(int,input().split())
    block[c-1].append(d-1)
    block[d-1].append(c-1)

def dfs(now):
    global group
    for next in friend[now]:
        tansaku.append(next)
    while tansaku:
        next=tansaku.pop()
        visited[next]=True
        group.append(next)
        for k in friend[next]:
            if visited[k]==True:
                continue 
            if k in tansaku:
                continue
            tansaku.append(k)
   
    """
    for next in friend[now]:
        if visited[next]==False:
            visited[next]=True
            group.append(next)
            dfs(next)
     """       
    return group
group=[]
tansaku=[]
visited=[False]*n
for i in range(n):
    if visited[i]==False:
        visited[i]=True
        g=set(dfs(i))|{i}
        

        for x in g:
            G[x]=list(g-{x})
        group=[]
for i in range(n):
    ans=set(G[i])-set(friend[i])-set(block[i])
    print(len(ans))



### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ
 
    def find(self, x):  # x の根を返す
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
            return self.parent[x]
 
    def unite(self, x, y):  # x, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
 
    def is_same(self, x, y):  # x, y が同じ集合に属するか判定する
        return self.find(x) == self.find(y)
 
    def group_size(self, x):  # x が属する集合の大きさを返す
        return self.size[self.find(x)]
 

n,m,k=map(int,input().split())
friend=[[]for i in range(n)]
block=[[]for i in range(n)]
group=[[]for i in range(n)]
uf=UnionFind(n)

for i in range(m):
    a,b=map(int,input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
    uf.unite(a-1,b-1)

for i in range(k):
    c,d=map(int,input().split())
    if uf.is_same(c-1,d-1):
        block[c-1].append(d-1)
        block[d-1].append(c-1)

for i in range(n):
    ans=uf.group_size(i)-1-len(friend[i])-len(block[i])
    print(ans)
### BUGGY CODE ###

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

for i in range(1, N + 1):
    print(A.count(i))

### FIXED CODE ###

from collections import Counter


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

c = Counter(A)
for i in range(1, N + 1):
    print(c[i])
### BUGGY CODE ###

S=input()

sum=0
judge=True

while judge:
    judge=False
    num=S.count("BW")
    sum+=num
    S=S.replace("BW","WB")
    if num!=0:
        judge=True

print(sum)


### FIXED CODE ###

# coding: utf-8
# Your code here!
S=input()
N=len(S)

sum=0
k=0

for i in range(N):
    if S[i]=="W":
        sum+=(i-k)
        k+=1

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

class SegmentTree:
    __slots__ = ('n', 'op', 'tree')

    def __init__(self, seq, op=max):
        self.n = len(seq)
        self.op = op
        self.tree = [-1] * (2 * self.n)

        for i in range(self.n):
            self.tree[i+self.n] = seq[i]

        for i in reversed(range(1, self.n)):
            self.tree[i] = op(self.tree[2*i], self.tree[2*i+1])

    def modify(self, pos, val):
        assert pos < self.n
        pos += self.n
        self.tree[pos] = val
        while pos > 1:
            self.tree[pos//2] = self.op(self.tree[pos], self.tree[pos ^ 1])
            pos //= 2

    def query(self, L, R):
        assert L <= R and L >= 0 and R <= self.n
        res = 0
        L += self.n
        R += self.n
        while L < R:
            if L % 2 == 1:
                res = self.op(res, self.tree[L])
                L += 1
            if R % 2 == 1:
                R -= 1
                res = self.op(res, self.tree[R])

            L //= 2
            R //= 2

        return res


def solve(n, heights, beauty):
    dp = SegmentTree([0] * (n+1), op=max)

    for pos, b in zip(heights, beauty):
        best = dp.query(0, pos)
        dp.modify(pos, best + b)

    return dp.query(0, n+1)


def main():
    n = int(input())
    heights = [int(c) for c in input().split()]
    beauty = [int(c) for c in input().split()]
    ans = solve(n, heights, beauty)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

n = int(input())
heights = [int(c) for c in input().split()]
beauty = [int(c) for c in input().split()]



base = 1
while base <= n:
    base *= 2

tree = [0] * (2 * base)

dp = [0] * (n+1)
for i in range(n):
    x = heights[i] + base
    best = 0
    while x > 1:
        if x % 2 == 1:
            best = max(best, tree[x-1])
        x //= 2

    dp[heights[i]] = best + beauty[i]

    j = base + heights[i]
    while j >= 1:
        tree[j] = max(tree[j], dp[heights[i]])
        j //= 2


    # for j in range(i):
    #     if heights[i] > heights[j] and beauty[i] + dp[j] > max_beauty:
    #         max_beauty = beauty[i] + dp[j]


ans = max(dp)
print(ans)
### BUGGY CODE ###

import collections

n = int(input())
s = input()
min_people = n - 1

def we_counter(pos):
  front = collections.Counter(s[:pos])
  back = collections.Counter(s[pos+1:])
  front_p = front['W']
  back_p = back['E']
  people = front_p + back_p
  return people


for i in range(n):
  people = we_counter(i)
  if people < min_people:
    min_people = people

print(min_people)


### FIXED CODE ###

n = int(input())
s = input()
point = [0]

def we_counter(pos):
  front = s[:pos]
  back = s[pos+1:]
  people = front.count('W') + back.count('E')
  return people


for i in range(n):
  if s[i] == 'W':
    point.append(point[i]-1)
  else:
    point.append(point[i]+1)

max_point = max(point)
pos = point.index(max_point)

print(we_counter(pos))
### BUGGY CODE ###

import numpy as np

s = [ord(a)-ord('a') for a in input()]
n = len(s)

if n == 2:
    if s[0] == s[1]:
        print('1 2')
    else:
        print('-1 -1')
    exit()

cnt = np.array([0] * 26)
cum = [cnt.copy()]

for i, a in enumerate(s):
    cnt[a] += 1
    cum.append(cnt.copy())

def is_check(cum, n):
    for i in [2, 3]:
        d = i // 2
        for j in range(n-i+1):
            for k in cum[j+i] - cum[j]:
                if k > d:
                    return j+1, j+i
    return -1, -1

print(' '.join(map(str, is_check(cum, len(s)))))

### FIXED CODE ###

import numpy as np

s = [ord(a)-ord('a') for a in input()]
n = len(s)

if n == 2:
    if s[0] == s[1]:
        print('1 2')
    else:
        print('-1 -1')
    exit()

cnt = np.array([0] * 26)
cum = [cnt.copy()]

for i, a in enumerate(s):
    cnt[a] += 1
    cum.append(cnt.copy())

def is_check(cum, n):
    i = 3
    d = 1
    for j in range(n-i+1):
        cum_ = cum[j+i] - cum[j]
        if cum_[cum_>1]:
            return j+1, j+i
    return -1, -1

print(' '.join(map(str, is_check(cum, len(s)))))
### BUGGY CODE ###

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
step = [0] * (n+1)
step[0] = 1
if 1 not in a:
    step[1] = 1
else:
    step[1] = 0
for i in range(2,n+1):
    if i in a:
        continue
    step[i] = step[i-1] + step[i-2]
step[-1] %= 1000000007
print(step[-1])

### FIXED CODE ###

n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
step = [0] * (n+1)
step[0] = 1
if 1 not in a:
    step[1] = 1
else:
    step[1] = 0
for i in range(2,n+1):
    if i in a:
        continue
    step[i] = (step[i-1] + step[i-2]) % 1000000007
print(step[-1])
### BUGGY CODE ###

# E - Dividing Chocolate
import sys
sys.setrecursionlimit(10000)

H,W,K = map(int,input().split())
S = [input() for _ in range(H)]
ans = 10000

def check(border, num):
    global H,W,K,S
    now = [0]*(num+1)
    add = 0
    for j in range(W):
        tmp = [0]*(num+1)
        for i in range(H):
            now[border[i]] += int(S[i][j])
            tmp[border[i]] += int(S[i][j])
        if max(now)>K:
            add += 1
            now = tmp
    return num+add

def rec(border, num, i):
    global H,W,K,S,ans
    if i<H:
        border[i] = num
        rec(border, num, i+1)
        border[i] = num+1
        rec(border, num+1, i+1)
    else:
        ans = min(ans, check(border, num))

rec([0]*H, 0, 1)
print(ans)

### FIXED CODE ###

# E - Dividing Chocolate
import sys
sys.setrecursionlimit(10000)

H,W,K = map(int,input().split())
S = [input() for _ in range(H)]
ans = 10000

def check(border, num):
    global H,W,K,S
    now = [0]*(num+1)
    add = 0
    for j in range(W):
        tmp = [0]*(num+1)
        for i in range(H):
            now[border[i]] += int(S[i][j])
            tmp[border[i]] += int(S[i][j])
        if max(now)>K:
            add += 1
            now = tmp
        if max(tmp)>K:
            return 10000
    return num+add

def rec(border, num, i):
    global H,W,K,S,ans
    if i<H:
        border[i] = num
        rec(border, num, i+1)
        border[i] = num+1
        rec(border, num+1, i+1)
    else:
        ans = min(ans, check(border, num))

rec([0]*H, 0, 1)
print(ans)
### BUGGY CODE ###

S = list(input())
Q = int(input())
rev = 0
for i in range(Q):
  query = input()
  if query == "1": rev = 1 - rev 
  elif int(query[2]) + rev == 2: S.append(query[4])
  else:  S.insert(0,query[4])
if rev == 1: S.reverse()  
print("".join(S))    

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
rev = 0
for i in range(Q):
  query = input()
  if query == "1": rev = 1 - rev 
  elif int(query[2]) + rev == 2: S.append(query[4])
  else:S.appendleft(query[4])
if rev == 1: S.reverse()  
print("".join(S))
### BUGGY CODE ###

import sys
import itertools

# import numpy as np

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

N, M = map(int, readline().split())
LR = [[int(x) for x in readline().split()] for _ in range(M)]
se = set(range(LR[0][0], LR[0][1]+1))
for i in LR:
    sa = set(range(i[0], i[1]+1))
    se = se & sa

print(len(se))



### FIXED CODE ###

import sys
import itertools

# import numpy as np

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

N, M = map(int, readline().split())
A = [None]*M
B = [None]*M
for i in range(M):
    A[i], B[i] = map(int, readline().split())

ans = min(B) - max(A)

print(ans + 1 if ans >= 0 else 0)
### BUGGY CODE ###

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

parent = [None]*N
depth = [0]*N
d = 0
queue = [0]
while queue:
    d += 1
    queue_new = []
    for q in queue:
        for e in E[q]:
            if e==parent[q]: continue
            parent[e] = q
            depth[e] = d
            queue_new.append(e)
    queue = queue_new

ancestor = [[None]*N for _ in range(N)]
for a in range(N):
    for b in range(a, N):
        _a = a
        _b = b
        while _a!=_b:
            if depth[_a] < depth[_b]: _b = parent[_b]
            else: _a = parent[_a]
        ancestor[a][b] = ancestor[b][a] = _a

M = int(input())
P = []
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    w = ancestor[u][v]
    path = set()
    while u!=w:
        _u = parent[u]
        path.add((u, _u))
        u = _u
    while v!=w:
        _v = parent[v]
        path.add((v, _v))
        v = _v
    P.append(path)


ans = 0
for k in range(2**M):
    path = set()
    n = 0
    for i in range(M):
        if (k>>i)&1:
            path |= P[i]
            n += 1

    if n==0: continue
    sign = +1 if n&1 else -1
    ans += sign * pow(2, N-1-len(path))
    
print(pow(2, N-1) - ans)

### FIXED CODE ###

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

parent = [None]*N
depth = [0]*N
d = 0
queue = [0]
while queue:
    d += 1
    queue_new = []
    for q in queue:
        for e in E[q]:
            if e==parent[q]: continue
            parent[e] = q
            depth[e] = d
            queue_new.append(e)
    queue = queue_new

ancestor = [[None]*N for _ in range(N)]
for a in range(N):
    for b in range(a, N):
        _a = a
        _b = b
        while _a!=_b:
            if depth[_a] < depth[_b]: _b = parent[_b]
            else: _a = parent[_a]
        ancestor[a][b] = ancestor[b][a] = _a

M = int(input())
P = []
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    w = ancestor[u][v]
    path = set()
    while u!=w:
        _u = parent[u]
        #path.add((u, _u))
        path.add(u*N+_u)
        u = _u
    while v!=w:
        _v = parent[v]
        #path.add((v, _v))
        path.add(v*N+_v)
        v = _v
    P.append(path)


ans = 0
n1 = N-1
for k in range(2**M):
    path = set()
    n = 0
    for i, p in enumerate(P):
        if (k>>i)&1:
            path |= p
            n += 1

    if n==0: continue
    sign = +1 if n&1 else -1
    ans += sign * pow(2, n1-len(path))
    
print(pow(2, N-1) - ans)
### BUGGY CODE ###

#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = 10 ** 18
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

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

dp = [[INF] * (N + 10) for _ in range(N + 10)]
dp2 = [[0] * (N + 10) for _ in range(N + 10)]

for l in range(N):
    dp[l][l] = a[l]

for i in range(N - 2, -1, -1):
    for j in range(i + 1, N):
        a = sorted([[dp[i][k] + dp2[k + 1][j] + dp2[i][k] + dp[k + 1][j], k] for k in range(i, j)])
        k = a[0][-1]
        dp[i][j] = dp[i][k] + dp[k + 1][j]
        dp2[i][j] = dp2[i][k] + dp[i][k] + dp2[k + 1][j] + dp[k+1][j]
print(dp2[0][N - 1])


### FIXED CODE ###

#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = 10 ** 18
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

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

dp = [[INF] * (N + 10) for _ in range(N + 10)]
dp2 = [[0] * (N + 10) for _ in range(N + 10)]

for l in range(N):
    dp[l][l] = a[l]

for i in range(N - 2, -1, -1):
    for j in range(i + 1, N):
        dp2[i][j] = min(dp[i][k] + dp2[k + 1][j] + dp2[i][k] + dp[k + 1][j] for k in range(i, j))
        for val in ([dp[i][k] + dp2[k + 1][j] + dp2[i][k] + dp[k + 1][j], k] for k in range(i, j)):
            if val[0] == dp2[i][j]:
                k = val[1]
        dp[i][j] = dp[i][k] + dp[k + 1][j]
print(dp2[0][N - 1])
### BUGGY CODE ###

from math import floor
a,b,n = map(int, input().split())
x = n
com = 0
while x >= 0:
    val = (a*x)//b-a*(x//b)
    if val < com:
        pass
    else:
        com = val
    x-=1
print(com)

### FIXED CODE ###

a,b,n = map(int, input().split())
com = 0
if n < b:
    x = n
else:
    x = b-1
val = (a*x)//b
print(val)