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

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

ans=-10**18
for i in range(n):
    start,count=i,1
    val=c[start]
    while p[start]-1 != i:
        start = p[start]-1
        count += 1
        val += c[start]
    start = i
    if val > 0:
        a = (k//count-1)*val
        ans=max(a,ans)
        num=count+k%count
    else:
        a=0
        num=min(k,count)
    for _ in range(num):
        a += c[start]
        start=p[start]-1
        ans=max(a,ans)
print(ans)

### FIXED CODE ###

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

ans=-10**18
for i in range(n):
    start,count=i,1
    val=c[start]
    while p[start]-1 != i:
        start = p[start]-1
        count += 1
        val += c[start]
    start = i
    if val > 0:
        a = (k//count-1)*val
        ans=max(a,ans)
        num=count+k%count
    else:
        a=0
        num=min(k,count)
    for _ in range(num):
        a += c[start]
        start=p[start]-1
        ans=max(a,ans)
print(ans)
### BUGGY CODE ###

h,w,m = map(int, input().split())
bh = []
bw = []
l_num = [0]*h
c_num = [0]*w
for i in range(m):
    i1, i2 = map(int, input().split())
    bh.append(i1)
    bw.append(i2)
    l_num[i1-1] = l_num[i1-1] + 1
    c_num[i2-1] = c_num[i2-1] + 1

#print(l_num,c_num)

l_candi = [i for i, v in enumerate(l_num) if v == max(l_num)]
c_candi = [i for i, v in enumerate(c_num) if v == max(c_num)]

#print(l_candi,c_candi)

t = 0
for k in range(m):
    if bh[k]-1 in l_candi and bw[k]-1 in c_candi:
        t = t + 1

if t < len(l_candi)*len(c_candi):
    print(max(l_num)+max(c_num))
else:
    print(max(l_num)+max(c_num)-1)


### FIXED CODE ###

h,w,m = map(int, input().split())
bh = []
bw = []
l_num = [0]*h
c_num = [0]*w
for i in range(m):
    i1, i2 = map(int, input().split())
    bh.append(i1)
    bw.append(i2)
    l_num[i1-1] = l_num[i1-1] + 1
    c_num[i2-1] = c_num[i2-1] + 1

#print(l_num,c_num)

max_l_num = max(l_num)
max_c_num = max(c_num)
l_candi = [i for i, v in enumerate(l_num) if v == max_l_num]
c_candi = [i for i, v in enumerate(c_num) if v == max_c_num]

#print(l_candi,c_candi)

t = 0
for k in range(m):
    if l_num[bh[k]-1] == max_l_num and c_num[bw[k]-1] == max_c_num:
        t = t + 1

if t < len(l_candi)*len(c_candi):
    print(max_l_num+max_c_num)
else:
    print(max_l_num+max_c_num-1)
### BUGGY CODE ###

import itertools

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

comb = []
if K % 2 != 0:
    for a, b, c in itertools.product(range(1, N//K+1), range(1, N//K+1), range(1, N//K+1)):
        comb.append((a, b, c))
else:
    for a, b, c in itertools.product(range(1, N//K+1), range(1, N//K+1), range(1, N//K+1)):
        comb.append((a*K, b*K, c*K))
    for a, b, c in itertools.product(range(1, (2*N+K)//(2*K)+1), range(1, (2*N+K)//(2*K)+1), range(1, (2*N+K)//(2*K)+1)):
        comb.append((a*K-K//2, b*K-K//2, c*K-K//2))


print(len(set(comb)))


### FIXED CODE ###

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

if K % 2 == 0:
    ans = (N//K)**3 + ((N+K//2)//K)**3
else:
    ans = (N//K)**3
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
h = sorted([int(input()) for _ in range(n)])
ans = 10**9
for i in range(n-k+1):
  tmp = max(h[i:i+k])-min(h[i:i+k])
  if ans > tmp:
    ans = tmp
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
h = sorted([int(input()) for _ in range(n)])
ans = 10**9
for i in range(k-1, n):
  ans = min(ans, h[i]-h[i-k+1])
print(ans)
### BUGGY CODE ###

import numpy as np

a = int(input())

print(np.array(range(a)).sum())

### FIXED CODE ###

from decimal import *
a = int(input())

print(int(Decimal((a -1)/2)*Decimal(a)))
### BUGGY CODE ###

N = int(input())

total = 0

while N > 0:
  total = (total + N % 10) % 9
  N = N // 10
  
if total % 9 == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

if sum([int(s) for s in list(input().split())]) % 9 == 0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

import math
n,a,b=list(map(int,input().split(" ")))

thenum=pow(10,9)+7


def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

ans=pow(2,n)%(thenum)-comb(n,a,thenum)-comb(n,b,thenum)-1
ans=ans%(10**9+7)
print(ans)



### FIXED CODE ###

import math
n,a,b=list(map(int,input().split(" ")))

mod = 1000000007

def choose(n, a):
    x = 1
    y = 1
    if n/2 < a:
        a = n - a
    for i in range(a):
        x *= n - i
        if x > mod:
            x %= mod
        y *= a - i
        if y > mod:
            y %= mod
    val = x * pow(y, mod-2, mod) % mod
    return val

ans=pow(2,n,mod)-choose(n,a)-choose(n,b)-1
ans=ans%(mod)
print(ans)
### BUGGY CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    A = [next(it) for i in range(N)]
    A.sort()
    AX2 = A[-1] // 2

    if N == 1:
        print(1)
        return
    if A[0] == 1:
        print(0 if A[1] == 1 else 1)
        return

    ax = []
    ans = j = 0

    i = 1
    while i < N:
        a0 = A[i-1]
        for x in ax:
            if a0 % x == 0:
                i += 1
                break
        else:
            if a0 <= AX2:
                ax.append(a0)
            if a0 == A[i]:
                for i in range(i+1, N):
                    if a0 != A[i]:
                        i += 1
                        break
                else:
                    break
                continue
            ans += 1
            i += 1

    if A[-2] != A[-1]:
        a0 = A[-1]
        for x in ax:
            if a0 % x == 0:
                break
        else:
            ans += 1

    print(ans)


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    A = [next(it) for i in range(N)]

    if N == 1:
        print(1)
        return

    ax = max(A)+1
    dp = [0]*ax
    for ai in A:
        da = dp[ai]
        if da > 1:
            continue
        dp[ai] += 1
        if da == 0:
            for aj in range(2*ai, ax, ai):
                dp[aj] = 2
        #print(dp)
    print(dp.count(1))


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

import sys
input = sys.stdin.readline

def main():
    N,M = map(int,input().split())
    X = [list(map(int,input().split())) for _ in range(N)]

    X.sort(key=lambda X:X[0])
    day = 1
    work = []
    payment = 0
    while day <= M:
        for i in range(N):
            if X[i][0] == day:
                work.append(X[i][1])
                work.sort()
        if work != []:
            payment += work.pop()
        day += 1

    print(payment)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline

def main():
    N,M = map(int,input().split())
    paylist = [[] for _ in range(M)]
    for _ in range(N):
        a,b = map(int,input().split())
        if M >= a:
            heapq.heappush(paylist[a-1],-b)
    work = []
    payment = 0
    for i in range(M):
        for j in paylist[i]:
            heapq.heappush(work,j)
        if work:
            payment += heapq.heappop(work)

    print(-payment)

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

import sys
input = sys.stdin.readline
h,w=map(int,input().split())
a=[]
for i in range(h):
    a.append(list(map(int,input().split())))
b=[]
for i in range(h):
    b.append(list(map(int,input().split())))
dp=[[set([]) for i in range(w)] for j in range(h)]
dp[0][0].add(a[0][0]-b[0][0])
dp[0][0].add(b[0][0]-a[0][0])
for i in range(h):
    for j in range(w):
        if i==j==0:
            continue
        if i==0:
            for k in dp[i][j-1]:
                if k<=3550:
                    dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                    dp[i][j].add(abs(k+b[i][j]-a[i][j]))
        elif j==0:
            for k in dp[i-1][j]:
                if k<=3550:
                    dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                    dp[i][j].add(abs(k+b[i][j]-a[i][j]))
        else:
            for k in (dp[i][j-1]|dp[i-1][j]):
                if k<=5500:
                    dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                    dp[i][j].add(abs(k+b[i][j]-a[i][j]))             
#dp[h-1][w-1]
ans=10**10
for i in dp[h-1][w-1]:
    ans=min(ans,abs(i))
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W=map(int,input().split())
a = [[] for _ in range(H)]
for i in range(H):
    a[i] = list(map(int, input().split()))
b = [[] for _ in range(H)]
for i in range(H):
    b[i] = list(map(int, input().split()))

for i in range(H):
    for j in range(W):
        a[i][j] =abs(a[i][j]-b[i][j])

dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(a[0][0])
for i in range(1,H):
    t = a[i][0]
    tmp = set()
    for k in dp[i-1][0]:
        tmp.add(k+t)
        tmp.add(abs(k-t))
    dp[i][0] = tmp
for j in range(1,W):
    t = a[0][j]
    tmp = set()
    for k in dp[0][j-1]:
        tmp.add(k+t)
        tmp.add(abs(k-t))
    dp[0][j] = tmp
for i in range(1,H):
    for j in range(1,W):
        t = a[i][j]
        tmp = set()
        for k in (dp[i-1][j] | dp[i][j-1]):
            tmp.add(k+t)
            tmp.add(abs(k-t))
        dp[i][j] = tmp
        dp[i-1][j-1] = set()

ls = list(dp[H-1][W-1])
print(min(ls))
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(e) for e in input().split()]
for _ in range(m):
  b, c = map(int, input().split())
  a.extend([c] * b)
a.sort(reverse = True)
print(sum(a[:n]))


### FIXED CODE ###

from functools import cmp_to_key
n, m = map(int, input().split())
a = [int(e) for e in input().split()]
bc = [[int(e) for e in input().split()] for _ in range(m)]
bc.sort(key = cmp_to_key(lambda x, y: y[1] - x[1]))
t = 0
for v in bc:
  b, c = v
  t += b
  a.extend([c] * b)
  if t > n:
    break
a.sort(reverse = True)
print(sum(a[:n]))
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.buffer.readline

def main():
    N,M = map(int,input().split())
    edge = [[] for _ in range(N)]
    
    for _ in range(M):
        a,b = map(int,input().split())
        a -= 1;b -= 1
        edge[a].append(b)
        edge[b].append(a)
        
    d = [10**10]*N
    d[0] = 0
    bef = [-1]*N
    
    q = deque([0])
    while q:
        now = q.pop()
        for fol in edge[now]:
            if d[fol] > d[now]+1:
                d[fol] = d[now]+1
                bef[fol] = now
                q.append(fol)

    if 10**10 not in d:
        print("Yes")
        for i in range(1,N):
            print(bef[i]+1)
    else:
        print("No")
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.buffer.readline

def main():
    N,M = map(int,input().split())
    edge = [[] for _ in range(N)]
    
    for _ in range(M):
        a,b = map(int,input().split())
        a -= 1;b -= 1
        edge[a].append(b)
        edge[b].append(a)
        
    go = [False]*N
    go[0] = True
    bef = [-1]*N
    
    q = deque([0])
    while q:
        now = q.popleft()
        for fol in edge[now]:
            if not go[fol]:
                bef[fol] = now
                go[fol] = True
                q.append(fol)

    if False in go:
        print("No")
    else:
        print("Yes")
        for i in range(1,N):
            print(bef[i]+1)

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

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
ans = 1
MOD = 10**9+7
MAX = 10**5+1
fact = [1] * MAX

for i, j in zip(a[:m-1], a[1:]):
    if j - i == 1:
        print(0)
        exit()

def comb_init():
    fact[0], fact[1] = 1, 1
    for i in range(2, MAX):
        fact[i] = fact[i-1] * i

def comb(n, r):
    return (fact[n]%MOD) * pow(fact[r], -1, MOD) * pow(fact[n-r], -1, MOD) 

def f(k):
    idx = k // 2
    num = 0
    for i in range(1, idx+1):
        num += comb(k-i, i)
        num %= MOD
    return num+1

comb_init()
for i in range(m+1):
    left = 0 if i == 0 else a[i-1] + 1
    right = n if i == m else a[i] - 1
    between = right - left
    ans *= f(between)
    ans %= MOD
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
ans = 1
MOD = 10**9+7
MAX = 10**5+1

fib = [0] * MAX
fib[0], fib[1] = 1, 2
for i, j in zip(a[:m-1], a[1:]):
    if j - i == 1:
        print(0)
        exit()

for i in range(2, MAX):
    fib[i] = fib[i-1] + fib[i-2]
    
for i in range(m+1):
    left = 0 if i == 0 else a[i-1] + 1
    right = n if i == m else a[i] - 1
    between = right - left
    if not between:
        continue
    ans *= fib[between-1]
    ans %= MOD
print(ans)
### BUGGY CODE ###

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

# solve

##. number of consecutive 0 groups and 1 groups
##. ex:
##.  s = '11101010110011'
##.       0: 0, 0, 0, 00
##.       1: 111, 1, 1, 11, 11
##.  zeros = [1, 1, 1, 2]
##.  ones = [3, 1, 1, 2, 2]
##.   (always count the edges of s as 1)
zeros = []
ones = []
_c = '1'
count = 0
for c in s:
	if _c == c:
		count += 1
	else:
		if _c == '0':
			zeros.append(count)
		else:
			ones.append(count)
		_c = c
		count = 1

if c == '0':
	zeros.append(count)
	ones.append(0)
else:
	ones.append(count)

if len(zeros) <= k:
	## flip all 0's
	ans = len(s)
else:
  ## flip k consecutive zero groups
  ans = 0
  i = 0
  while i + k <= len(zeros):
	  _ans = sum(zeros[i:i+k]) + sum(ones[i:i+k+1])
	  ans = max(ans, _ans)
	  i += 1

print(ans)

### FIXED CODE ###

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

# solve

##. number of consecutive 0 groups and 1 groups
##. ex:
##.  s = '11101010110011'
##.       0: 0, 0, 0, 00
##.       1: 111, 1, 1, 11, 11
##.  zeros = [1, 1, 1, 2]
##.  ones = [3, 1, 1, 2, 2]
##.   (always count the edges of s as 1)
zeros = []
ones = []
_c = '1'
count = 0
for c in s:
	if _c == c:
		count += 1
	else:
		if _c == '0':
			zeros.append(count)
		else:
			ones.append(count)
		_c = c
		count = 1

if c == '0':
	zeros.append(count)
	ones.append(0)
else:
	ones.append(count)

if len(zeros) <= k:
	## flip all 0's
	ans = len(s)
else:
  ## flip k consecutive zero groups
  ans = 0

  i = 0
  _ans = sum(zeros[i:i+k]) + sum(ones[i:i+k+1])
  ans = _ans

  i = 1
  while i + k <= len(zeros):
#	  _ans = sum(zeros[i:i+k]) + sum(ones[i:i+k+1])
	  _ans += zeros[i+k-1] - zeros[i-1] + ones[i+k] - ones[i-1]
	  ans = max(ans, _ans)
	  i += 1

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

import sys


def main():
    N, K = map(int, sys.stdin.readline().rstrip().split())
    L = [0] * 10
    R = [0] * 10
    for i in range(K):
        l, r = map(int, sys.stdin.readline().rstrip().split())
        L[i], R[i] = l, r

    dp = [0] * (N+1)
    dp[1] = 1
    for i in range(2,N+1):
        for j in range(K):
            l = min(L[j], i)
            r = min(R[j], i)
            dp[i] += sum(dp[i-r:(i-l)+1])
            dp[i] %= 998244353
        # print(dp[i])
    
    print(dp[N])


main()

### FIXED CODE ###

import sys


def main():
    N, K = map(int, sys.stdin.readline().rstrip().split())
    L = [0] * 10
    R = [0] * 10
    for i in range(K):
        l, r = map(int, sys.stdin.readline().rstrip().split())
        L[i], R[i] = l, r

    dp = [0] * (N + 1)
    up = [0] * (N + 1)
    up[0] = 1
    up[1] = -1
    for i in range(1, N + 1):
        dp[i] = dp[i - 1] + up[i - 1]
        for j in range(K):
            if i + (L[j] - 1) < N + 1:
                up[i + (L[j] - 1)] += dp[i]
            if i + R[j] < N + 1:
                up[i + R[j]] -= dp[i]
        dp[i] %= 998244353

    print(dp[N])


main()
### BUGGY CODE ###

import math
a, b, n = map(int, input().split())
max_i = 0
for i in range(1, n+1):
    tmp = math.floor(a*i/b)- a * math.floor(i/b)
    if tmp > max_i:
        max_i = tmp
print(max_i)

### FIXED CODE ###

import math
a, b, n = map(int, input().split())
x = min(b-1, n)
ans = math.floor(a*x/b)- a * math.floor(x/b)
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    graph[u].append(v)
S, T = map(int, input().split())
S, T = S-1, T-1
def bfs3(v, n, ans):
    if n == 0:
        ans.append(v)
    else:
        for u in graph[v]:
            bfs3(u, n-1,ans)

visit = [False for i in range(N)]
length = [0 for i in range(N)]
def bfs(v, T):
    Q = []
    Q.append(v)
    visit[v] = True
    while len(Q) > 0:
        v = Q.pop(0)
        ans = []
        bfs3(v, 3, ans)
        con = list(set(ans))
        #print(con)
        for u in con:
            if not visit[u]:
                visit[u] = True
                length[u] = length[v] + 1
                Q.append(u)
                #print(u, length[u])
            if u == T:
                return()
bfs(S,T)
#print(length)
if visit[T]:
    print(length[T])
else:
    print(-1)


### FIXED CODE ###

N, M = map(int, input().split())
graph = [[] for i in range(3 * N)]
for i in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    graph[u].append(v+N)
    graph[u+N].append(v+2*N)
    graph[u+2*N].append(v)
S, T = map(int,input().split())
S, T = S-1, T-1
visit = [False for i in range(3 * N)]
length = [0 for i in range(3 * N)]
def bfs(v):
    Q = []
    Q.append(v)
    visit[v] = True
    while Q:
        v = Q.pop(0)
        for u in graph[v]:
            if not visit[u]:
                visit[u] = True
                length[u] = length[v] + 1
                Q.append(u)
                #print(u, length[u])
bfs(S)
#print(length)
if visit[T]:
    print(int(length[T] //3))
else:
    print(-1)
### BUGGY CODE ###

N = int(input())
S = list(input())
ans = 0
for i in range(N):
    for j in range(i+1,N):
        if S[i] != S[j]:
            for k in range(j+1,N):
                if S[i] != S[j] and S[j] != S[k] and S[i] != S[k] and j-i != k-j:
                    ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
S = list(input())
R = S.count('R')
G = S.count('G')
B = S.count('B')
ans = R*G*B
for i in range(N):
    for k in range(i+1,N):
        if (k+i)%2 == 1:
            continue
        else:
            j = (k+i)//2
            if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
                ans -= 1
print(ans)
### BUGGY CODE ###

n = int(input())

print(0)
sex = input()
if sex == "Vacant":
    exit(0)
axis = sex

left = 1
right = n

while left + 1 < right:
    mid = (left + right) // 2
    print(mid)
    sex = input()
    if sex == "Vacant":
        exit(0)
    elif sex == axis:
        left = mid + 1
    else:
        right = mid

print(left)
exit(0)



### FIXED CODE ###

def val(num):
    print(num, flush=True)
    sex = input()
    if sex == "Vacant":
        exit(0)
    return 1 if sex == "Male" else 0


n = int(input())

l_sex = val(0)
r_sex = val(n - 1)

left = 0
right = n - 1

while left < right:
    mid = (left + right) // 2
    sex = val(mid)
    if (mid - left) % 2 == 0 and sex != l_sex:
        right = mid
        r_sex = sex
    elif (mid - left) % 2 == 1 and sex == l_sex:
        right = mid
        r_sex = sex
    else:
        left = mid
        l_sex = sex

print(left, flush=True)
exit(0)
### BUGGY CODE ###

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

x = []
for i in range(q):
  x.append(list(map(int, input().split())))

for i in x:
  print(s[i[0] - 1:i[1]].count('AC'))

### FIXED CODE ###

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


a = [0] * (n + 1)

# n文字目までにACが出た回数を累積和で求める
for i in range(n):
  a[i + 1] = a[i] + (1 if s[i:i + 2] == 'AC' else 0)

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

N = int(input())
A = [0] * N
A[0] = int(input())
for i in range(1, N):
	A[i] = int(input())
	if A[i] in A[: i]:
		A[A[: i].index(A[i])] = -1
		A[i] = -1

print(len([k for k in A if k != -1]))


### FIXED CODE ###

from collections import Counter

N = int(input())
A = [int(input()) for _ in range(N)]
c = Counter(A).values()

print(len([i for i in c if i % 2 == 1]))
### BUGGY CODE ###

from collections import defaultdict, deque

S = input()

L = deque()
D1 = defaultdict(set)
D2 = {}
for i in range(len(S)-3):
  for j in range(i+4, len(S)+1):
    X = int(S[i:j])
    r = X % 2019
    if r == 0:
      L.append(i)
      D1[i].add(j)
      D2[j] = i
      break

for x in reversed(L):
  if x in D2:
    D1[D2[x]] += D1[x]
print(sum(len(x) for x in D1.values()))

### FIXED CODE ###

from collections import defaultdict

S = input()

D = defaultdict(int)
D[0] += 1
x = 0
d = 1
for s in reversed(S):
  x = (x + int(s) * d) % 2019
  D[x] += 1
  d = (d * 10) % 2019

print(sum(x * (x-1) // 2 for x in D.values()))
### BUGGY CODE ###

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

k_y = [1000]
k_y_new = [ 1000 ]
for i in range(n):
	for hk,hy in enumerate(k_y): #所持株、金
		kk = 0#想定所持株数
		while True:
			genkin = (hk - kk) * a[i] + hy
			
			if genkin < 0 :
				break
			else:
				if kk >= len(k_y_new):
					k_y_new.append( genkin )
				else:
					k_y_new[kk] = max(k_y_new[kk], genkin)
				kk = kk + 1
		#print( k_y_new )
	k_y = [y for y in k_y_new]
print( k_y_new[0] )



### FIXED CODE ###

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

k_y = [1000]
yen = 1000
resyen = 1000
kabu_max = 0
for i in range(n):
	#株を売り払うケース
	newyen = max( yen, kabu_max * a[i] + resyen)
	
	#株を最大買うケース
	kabu_max_new = max( kabu_max + resyen // a[i], yen // a[i] )
	if kabu_max_new == yen // a[i]:
		if kabu_max_new == kabu_max + resyen // a[i]:
			resyen = max( yen % a[i], resyen % a[i])
		else:
			resyen = yen % a[i]
	
	yen = newyen
	kabu_max = kabu_max_new
	#print(kabu_max,yen,resyen)
print( yen )
### BUGGY CODE ###

N = int(input())

ans =0

for i in range(1,N+1):
    x = (N+1)/i
    R= round(x, 0)
    for n in range(1,int(R)+1):
        if  i*n < N:
            ans +=1
print(ans)

### FIXED CODE ###

N = int(input())

ans =0

for i in range(1,N):
    ans += (N-1)//i
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python

def main():
    n = int(input())
    a = list(map(int, input().split()))

    cnt = 0

    for i in range(n-1):
        b = a[i]
        c = 0
        for j in range(i+b, n):
            if a[j] == c:
                cnt += 1
            c += 1
    print(cnt)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python

def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnt = 0

    lst1 = [0] * n
    lst2 = [0] * n

    for i in range(1, n+1):
        p = i - a[i-1]
        q = i + a[i-1]

        if 0 <= p < n:
            lst1[p] += 1
        if 0 <= q < n:
            lst2[q] += 1

    for i in range(n):
        cnt += lst1[i] * lst2[i]

    print(cnt)

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

a = input()
k, s = a.split(' ')
K = int(k)
S = int(s)
ans = 0
for x in range(K + 1):
    for y in range(K + 1):
        for z in range(K + 1):
            if (x + y + z) == S:
                ans += 1

print(ans)

### FIXED CODE ###

a = input()
k, s = a.split(' ')
K = int(k)
S = int(s)
ans = 0
for x in range(K + 1):
    for y in range(K + 1):
        z = S - x - y
        if (z >= 0) and (z <= K):
            ans += 1

print(ans)