Harryxun/stf_run huggingface dataset:
from sys import stdin
from collections import deque
def I(): return int(stdin.readline().rstrip())
def LI(): return list(map(int,stdin.readline().rstrip().split()))
 
def end():
    print(-1)
    exit()
 
def main():
    n = I()
    deq = deque(LI())
    if n==0:
        if deq[0] == 0:
            print(1)
            exit()
    if deq[0]!=0:
        end()
    max = deque()
    for i in range(n,-1,-1):
        if 2**i<deq[i]:
            end()
        if i == n:
            max.appendleft(deq[i])
        else:
            max.appendleft(max[0]+deq[i])
    for i in range(n+1):
        max[i] = min(2**i,max[i])
        if i!=n and i!=0:
            max[i] = min(2*(max[i-1]-deq[i-1]),max[i])
    	if max[i]<deq[i]:
          end()
    print(sum(max))
    return
 
if __name__=='__main__':
    main()

### FIXED CODE ###

from sys import stdin
from collections import deque
def I(): return int(stdin.readline().rstrip())
def LI(): return list(map(int,stdin.readline().rstrip().split()))
 
def end():
    print(-1)
    exit()
 
def main():
    n = I()
    a = deque(LI())
    if n==0:
        if a[0] == 1:
            print(1)
            exit()
        else:
            end()
    elif a[0]!=0:
        end()

    b = [0]*(n+1)
    for i in range(n,-1,-1):
        if i == n:
            b[i] = a[i]
        else:
            b[i] = min(b[i+1]+a[i],2**i)

    for i in range(n+1):
        if i!=0:
            b[i] = min(2*(b[i-1]-a[i-1]),b[i])
        if b[i]<a[i]:
            end()
    print(sum(b))
    return
 
if __name__=='__main__':
    main()
A,B,C = map(int, input(),split())
L = sorted([A,B,C])
print(10*L[0]+L[1]+L[2])

### FIXED CODE ###

A,B,C = map(int, input().split())
L = sorted([A,B,C])
print(10*L[2]+L[1]+L[0])
n,x=map(int,input().split())
d=0
cnt=0
l=list(map(int,input().split()))
while(d<=x):
  cnt+=1
  d+=l[cnt-1]
print(cnt)

### FIXED CODE ###

n,x=map(int,input().split())
d=0
cnt=0
l=list(map(int,input().split()))
while(d<=x):
  cnt+=1
  if cnt==n+1:
    break
  d+=l[cnt-1]
print(cnt)
import sys
import numpy as np
from functools import reduce

def subset(line):
    l = line.strip().split(" ")
    a = list(map(int, l))
    xy = list(map(lambda x: [x // 10, x % 10], a))
    dominos = [[1 if x != y and ([x, y] in xy or [y, x] in xy) else 0 \
                for x in range(0, 7)] for y in range(0, 7)]  
    digits = np.unique(np.sort(reduce(lambda x, y: x + y, xy)))
    return digits, dominos

def is_connected(d, g):
    a = np.array(g)
    z = np.zeros_like(a)
    b = a
    for i in range(1, z.shape[0]):
        z += b
        b = b.dot(a)
    zz = z[d[0]][d]
    return len(zz[zz == 0]) == 0

lno = 0
for line in sys.stdin:
    lno += 1
    if lno == 1:
        n = int(line)
    else:
        digits, dominos = subset(line)
        if not is_connected(digits, dominos):
            print("No")
        else:
            order = np.sum(dominos, axis = 0)
            order = order % 2
            if np.all(order == 0):
                print("Yes")
            elif len(order[order == 1]) <= 2:
                print("Yes")
            else:
                print("No")
        lno = 0


### FIXED CODE ###

import sys

def subset(line):
    l = line.strip().split(" ")
    a = list(map(int, l))
    xy = list(map(lambda x: [x // 10, x % 10], a))
    dominos = [[2 if [x, y] in xy and x == y else \
                1 if [x, y] in xy else \
                1 if [y, x] in xy else 0 \
                for x in range(0, 7)] for y in range(0, 7)] 
    digits = []
    for i in xy:
        digits.extend(i)
    digits = list(set(digits))
    digits.sort()
    return digits, dominos

def add_matrix(a, b):
    c = [[a[j][i] + b[j][i] for i in range(0, 7)] for j in range(0, 7)]
    return c

def mul_matrix(a, b):
    c = [[0 for i in range(0, 7)] for j in range(0, 7)]
    for j in range(0, 7):
        for i in range(0, 7):
            for k in range(0, 7):
                c[j][i] += a[j][k] * b[k][i]
    return c
                
def is_connected(d, g):
    a = g[:]
    z = [[0 for i in range(0, 7)] for j in range(0, 7)]
    b = a
    for i in range(0, 7):
        z = add_matrix(z, b)
        b = mul_matrix(b, a)
    zeros = 0
    for i in d:
        if z[d[0]][i] == 0:
            zeros += 1
    return zeros == 0
        
lno = 0
for line in sys.stdin:
    lno += 1
    if lno == 1:
        n = int(line)
    else:
        digits, dominos = subset(line)
        if not is_connected(digits, dominos):
            print("No")
        else:
            order = [sum(dominos[i]) for i in range(0, 7)]
            odd = 0
            for i in digits:
                if order[i] % 2 != 0:
                    odd += 1
            if odd <= 2:
                print("Yes")
            else:
                print("No")
        lno = 0
n, k = [ int(v) for v in input().split() ]
num = [ int(v) for v in input().split() ]
num_2 = [ max(i,0) for i in num ] 


cum_num, cum_num_2 = [0] + cumsum(num), [0] + cumsum(num_2)

ans = 0
for i in range(n-k+1):
    ansl = cum_num_2[i]
    ansm = cum_num[k+i] - cum_num[i]
    ansr = cum_num_2[n] - cum_num_2[i+k]
    ans = max(ansl+max(ansm,0)+ansr, ans)
print(ans)

### FIXED CODE ###

def cumsum(inlist):
    s = 0
    outlist = []
    for i in inlist:
        s += i
        outlist.append(s)
    return outlist


n, k = [ int(v) for v in input().split() ]
num = [ int(v) for v in input().split() ]
num_2 = [ max(i,0) for i in num ] 


cum_num, cum_num_2 = [0] + cumsum(num), [0] + cumsum(num_2)

ans = 0
for i in range(n-k+1):
    ansl = cum_num_2[i]
    ansm = cum_num[k+i] - cum_num[i]
    ansr = cum_num_2[n] - cum_num_2[i+k]
    ans = max(ansl+max(ansm,0)+ansr, ans)
print(ans)
N = int(input())
hs = list(map(int, input().split()))

costs_1 = 0
costs_2 = abs(hs[1] - hs[0])
for i in range(2, N):
  costs1, costs2 = min(costs1 + abs(h[i] - h[i - 2]), costs2 + abs(h[i] - h[i - 2])), costs1
  
print(costs2)

### FIXED CODE ###

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

costs1 = 0
costs2 = abs(hs[1] - hs[0])
for i in range(2, N):
  costs1, costs2 = costs2, min(costs1 + abs(hs[i] - hs[i - 2]), costs2 + abs(hs[i] - hs[i - 1])),
  
print(costs2)
def main(N,M,a):
    dp = [-1]*N
    dp[0] = 1
    dp[1] = 2
    for i in a:
        if i == 1:
            dp[0] = 0
            dp[1] = 1
        else:
            dp[i-1] = 0
    for i in range(2,N):
        if dp[i] != 0:
            dp[i] = dp[i-1] + dp[i-2]
    return dp[-1]
N,M = map(int, input().split())
a = list(int(input()) for i in range(M))

print(main(N,M,a) % 1000000007)

### FIXED CODE ###

def main(N,M,a):
    dp = [-1]*N
    dp[0] = 1
    if N != 1:
        dp[1] = 2
    for i in a:
        if i == 1:
            dp[0] = 0
            dp[1] = 1
        else:
            dp[i-1] = 0
    for i in range(2,N):
        if dp[i] != 0:
            dp[i] = dp[i-1] + dp[i-2]
    return dp[-1]
N,M = map(int, input().split())
a = list(int(input()) for i in range(M))

print(main(N,M,a) % 1000000007)
n,x=map(int,input().split())
a=list(map(int,input().split()))
sum=0
count=1
for i in range(x):
  sum+=a[i]
  if sum<=x:
    count+=1
print(count)


### FIXED CODE ###

n,x=map(int,input().split())
a=list(map(int,input().split()))
sum=0
count=1
for i in range(n):
  sum+=a[i]
  if sum<=x:
    count+=1
print(count)
a,b=map(int,input())
s=list(input())
if s[:a].isnumeric() and s[a]=="-" and s[a+1:].isnumeric():
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a,b=map(int,input().split())
s=str(input())
if s[:a].isnumeric() and s[a]=="-" and s[a+1:].isnumeric():
    print("Yes")
else:
    print("No")
import math
n=int(input())
a=map(int, input().split())
print(min(a), max(a), sum(a))

### FIXED CODE ###

n=int(input())
a=list(map(int, input().rstrip().split()))
print(min(a), max(a), sum(a))
X = [0,0,0]

n = int(input())
A = [int(x) for x in input().split()]

res = 1
for a in A:
    res = res*X.count(a) % 1000000007
    if X.count(a):
        X[X.index(a)] += 1
    else:
        assert False
print(res)


### FIXED CODE ###

import sys

X = [0,0,0]

n = int(input())
A = [int(x) for x in input().split()]

res = 1
for a in A:
    res = res*X.count(a) % 1000000007
    if X.count(a):
        X[X.index(a)] += 1
    else:
        print(0)
        sys.exit(0)
print(res)
n=int(input())
flag=0
for i in range(9):
  nn=n/(i+1)
  if(nn<10 and type(nn)==int):
    flag=1
    break:
if(flag):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n=int(input())
flag=0
for i in range(9):
  nn=n/(i+1)
  if(nn<10 and (nn.is_integer())):
    flag=1
    break
if(flag):
  print("Yes")
else:
  print("No")
N = int(input())
l = [list(map(int, input().split())) for i in range(n)]
l.sort(key= lambda x:x[1])
t=0
for i in l:
    a,b=i
    t+=a
    if(t>b):
        print("No")
        break
    else:
        print("Yes");


### FIXED CODE ###

N = int(input())
l = [list(map(int, input().split())) for i in range(N)]
l.sort(key= lambda x:x[1])
t=0
cnt=0
for i in l:
    cnt+=1
    a,b=i
    t+=a
    if(t>b):
        print("No")
        break
    elif cnt==N:
        print("Yes");
N=input()
i=(int(N[:-3])+1)*1000


j=i-int(N)

if j>999:
  print(0)
else:
  print(j)


### FIXED CODE ###

N=input()
if len(N)>3:
    i=(int(N[:-3])+1)*1000
else:
    i=1000

j=i-int(N)

if j>999:
  print(0)
else:
  print(j)
n=int(input())  #数値入力 「N」だけの入力のとき
c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
d=[i for i in range(1,n+1)]
f=0
for i in range(n):
    if d[i]-d[i]:
        f+=1
if f == 0 or f == 2:
    print("YES")
else:
    print("NO)

### FIXED CODE ###

n=int(input())  #数値入力 「N」だけの入力のとき
#n= 5  #数値入力 「N」だけの入力のとき
c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
#c=[5, 2, 3, 4, 1]
d=[i for i in range(1,n+1)]
f=0
for i in range(n):
    if c[i]-d[i]:
        f+=1
#print(f)
if f == 0 or f == 2:
    print("YES")
else:
    print("NO")
100 50 4


### FIXED CODE ###

# coding: utf-8
# Your code here!

a,b,k = map(int, input().split())

def d(n):
    div = []
    for i in range(1,n+1):
        if(n % i == 0):
            div.append(i)
    return div
        
a_d = d(a)
b_d = d(b)
s = []
l = []
ab = []

if len(a_d) < len(b_d):
    s = a_d
    l = b_d
else:
    s = b_d
    l = a_d

for i in s:
    if i in l:
        ab.append(i)
print(ab[len(ab)-k])
N,Q=map(int,(input()).split())
S=input()
l_list=[]
r_list=[]
for i in range(Q):
  l,r=input().split()
  l_list.append(int(l))
  r_list.append(int(r))
for i in range(Q):
  S_i=S[int(l_list[i])-1,int(r_list[i])]
  n=0
  while "AC" in S_i:
    n+=1
  print(n)


### FIXED CODE ###

N,Q=map(int,(input()).split())
S=input()
l_list=[]
r_list=[]
for i in range(Q):
  l,r=input().split()
  l_list.append(int(l))
  r_list.append(int(r))
count=0
AC_count=[0]
for i in range(1,N+2):
  if S[i-1:i+1]=="AC":
    count+=1
  AC_count.append(count)
AC_count.append(count)
k=0
for j in range(Q):
  k=AC_count[r_list[j]-1]-AC_count[l_list[j]-1]
  print(k)
input = input()
num = 0

for i in range(2):
  if (input[i] == 1):
    num++

print(i)

### FIXED CODE ###

input = str(input())
num = 0

for i in input:
  if i == "1":
    num += 1
    
print(num)
def main():
  N = int(input())
  A = list(map(int,input().split()))
  ans = 0
  for i in range(1,N):
    sub = A[i-1] - A[i]
    if sub > 0:
      A[i]+=sub
      ans+=sub
  print(sub)
  return
main()

### FIXED CODE ###

def main():
  N = int(input())
  A = list(map(int,input().split()))
  ans = 0
  for i in range(1,N):
    sub = A[i-1] - A[i]
    if sub > 0:
      A[i]+=sub
      ans+=sub
  print(ans)
  return
main()
print(1110-int(inpout()))

### FIXED CODE ###

print(1110-int(input()))
K = int(input())
print(K)
X = int(input())
print(X)

if 500*K >= X:
	print("Yes")
else:
	print("No")

### FIXED CODE ###

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

if 500*K >= X:
    print("Yes")
else:
    print("No")
a = input()
b = input()
print(a*b,2*a+2*b)

### FIXED CODE ###

a,b=map(int,input().split())
print(a*b,2*a+2*b)
a, b = map(int,raw_input().split())

if a > b:
 print("a > b")

elif a < b:
 print("a < b")

else:
 print("a == b")

### FIXED CODE ###

a, b = map(int, input().split())
if a < b:
    print('a < b')
elif a > b:
    print('a > b')
else:
    print('a == b')
N,L = map(int,input().split())
 
for n in range(int(N)):
    data.append(input())
 
 
    
result=sorted(data)
result

### FIXED CODE ###

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

data=[]
for n in range(int(N)):
    data.append(input())
  
iroha=""
A=sorted(data)
for i in A:
    iroha+=i
    
print(iroha)
n = int(input())
x = list(map(int,input().split()))
j = max(x)
m = 0
y = True

for p in range(n):
    if x[0] != x[i]:
        y = False

if y:
    print(0)
    exit(0)

for p in range(j):
    c = 0
    z = 0
    for i in range(n):
        z = x[i] - p
        c = c + (z * z)
    
    if m == 0:
        m = c
    else:
        if m > c:
            m = c

print(m)

### FIXED CODE ###

n = int(input())
x = list(map(int,input().split()))
j = max(x)
m = 0
y = True

for i in range(n):
    if x[0] != x[i]:
        y = False

if y:
    print(0)
    exit(0)

for p in range(j):
    c = 0
    z = 0
    for i in range(n):
        z = x[i] - p
        c = c + (z * z)
    
    if m == 0:
        m = c
    else:
        if m > c:
            m = c

print(m)
N M = map(int,input().split())
List = list(map(int,input().split()))
print(N-sum(List) if N-sum(List) >= 0 else -1)


### FIXED CODE ###

N,M= map(int,input().split())
List = list(map(int,input().split()))
print(N-sum(List) if N-sum(List) >= 0 else -1)
d = int(input()))
 
d = set(d)
print(len(d))

### FIXED CODE ###

n = int(input())

di = set(map(int, [input() for i in range(n)]))

print(len(di))
import numpy as np
from copy import deepcopy
temp=list(map(int, input().split()))
R=temp[0]
C=temp[1]

color=np.zeros((R,C)).astype(int)

for i in range(R):
  temp=input()
  a=np.zeros(C).astype(int)
  for j in range(C):
      if temp[j]=='#':
        a[j]=1
      else:
        a[j]=0
  color[i]=a
  
def Adj(u):
  adj=[]
  for v in [(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]-1),(u[0],u[1]+1)]:
      if v[0]>=0 and v[0]<R and v[1]>=0 and v[1]<C:
        adj.append(v)
  return adj  

def BFS(s,c,d):
  Q=[s]
  while Q !=[]:
    u=Q[0]
    del Q[0]
    for v in Adj(u):  
      if c[v[0],v[1]]==0:
        c[v[0],v[1]]=1
        d[v[0],v[1]]=d[u[0],u[1]]+1
        Q.append(v)
  return ma
        
def main():
  ma=0
  for sx in range(R):
    for sy in range(C):
      if color[sx,sy]==0:
        d=np.zeros((R,C)).astype(int)
        c=deepcopy(color)
        c[sx,sy]=1
        BFS((sx,sy),c,d)
        ma=max(np.max(d),ma)
  print(ma)

main()


### FIXED CODE ###

import numpy as np
from copy import deepcopy
temp=list(map(int, input().split()))
R=temp[0]
C=temp[1]

color=np.zeros((R,C)).astype(int)

for i in range(R):
  temp=input()
  a=np.zeros(C).astype(int)
  for j in range(C):
      if temp[j]=='#':
        a[j]=1
      else:
        a[j]=0
  color[i]=a
  
def Adj(u):
  adj=[]
  for v in [(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]-1),(u[0],u[1]+1)]:
      if v[0]>=0 and v[0]<R and v[1]>=0 and v[1]<C:
        adj.append(v)
  return adj  

def BFS(s,c,d):
  ma=0
  Q=[s]
  while Q !=[]:
    u=Q[0]
    del Q[0]
    if d[u[0],u[1]]>ma:
      ma=d[u[0],u[1]]
    for v in Adj(u):  
      if c[v[0],v[1]]==0:
        c[v[0],v[1]]=1
        d[v[0],v[1]]=d[u[0],u[1]]+1
        Q.append(v)
  return ma
        
def main():
  ma=0
  for sx in range(R):
    for sy in range(C):
      if color[sx,sy]==0:
        d=np.zeros((R,C)).astype(int)
        c=deepcopy(color)
        c[sx,sy]=1
        ma=max(BFS((sx,sy),c,d),ma)
  print(ma)

main()
n,m= map(int,input().split())
inputs = []
for _ in range(m):
    inputs.append(list(map(int,input().split())))

if n == 1:
    if len([i[1] for i in inputs if i[1] != inputs[0][1]]) > 1:
        print(-1)
        exit()
    else:
        print(max(0,inputs[0][1]))
else:
    out = [-1] * n
    for item in inputs:
        s = item[0]
        c = item[1]
        if out[s-1] != -1 and out[s-1] != c:
            print(-1)
            exit()
        else:
            out[s-1] = c

out[0] = max(out[0],1)
res = 0
for i in range(len(out)):
    if out[i] != -1:
        res += out[i] * 10 ** (n-i-1)
print(res)
        

### FIXED CODE ###

n,m= map(int,input().split())
inputs = []
for _ in range(m):
    inputs.append(list(map(int,input().split())))

if m == 0:
    if n == 1:
        print(0)
    else:
        print(10**(n-1))
    exit()
elif n == 1:
    if len([i[1] for i in inputs if i[1] != inputs[0][1]]) > 0:
        print(-1)    
    else:
        print(max(0,inputs[0][1]))
    exit()
else:
    out = [-1] * n
    for item in inputs:
        s = item[0]
        c = item[1]
        if out[s-1] != -1 and out[s-1] != c:
            print(-1)
            exit()
        elif s == 1 and c == 0:
            print(-1)
            exit()
        else:
            out[s-1] = c

out[0] = max(out[0],1)
res = 0
for i in range(len(out)):
    if out[i] != -1:
        res += out[i] * 10 ** (n-i-1)
print(res)
a = input()
ans = 0
for i in range(2**(len(a)-1)):
    b = format(i, 'b').zfill((len(a)-1))
    li = []
    num = [a[0]]
    for i in range(len(b)):
        if b[i] == '1':
            ans += int(''.join(num))
            num = [a[i+1]]
        else:
            num.append(a[i+1])
    ans += int(''.join(num))

print(ans)

### FIXED CODE ###

a = input()
if len(a) == 1:
    print(int(a))
    exit()
ans = 0
for i in range(2**(len(a)-1)):
    b = format(i, 'b').zfill((len(a)-1))
    li = []
    num = [a[0]]
    for i in range(len(b)):
        if b[i] == '1':
            ans += int(''.join(num))
            num = [a[i+1]]
        else:
            num.append(a[i+1])
    ans += int(''.join(num))

print(ans)
#ABC 144 C - Walk on Multiplication Table
N = int(input())

import math 
def get_prime(n):
    
    if n <=1:
        return []
    prime = [2]
    limit = int(math.sqrt(n))
    
    # 奇数のリストを作成
    data = [i+1 for i in range(2,n,2)]
    while limit > data[0]:
        prime.append(data[0])
        data = [j for j in data if j % data[0] !=0]
    return prime + data
from itertools import combinations
import functools
import operator
P = get_prime(N)
m = N+1
memo = []
for i in range(1,len(P)+1):
    L1 = list(combinations(P,i))
    L1 = [list(l) for l in L1]
    for l in L1:
        if l not in memo:
            memo.append(l)
            s1 = functools.reduce(operator.mul,l)
            s2 = N/s1
            if s1+s2 <=m:
                m = s1+s2
print(int(m-2))

### FIXED CODE ###

N = int(input())
ans = N*3
for i in range(1,int(N**0.5)+1):
    if N%i==0:
        s1 = i
        s2 =N/i
        
        if ans > s1+s2:
            ans =int(s1+s2)
print(ans-2)
X,Y,A,B,C=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))
p.sort()
q.sort()
p.reverse()
q.reverse()
p=p[:X]
q=q[:Y]
r=r[:max(X,Y)]
 
a=p[:]
a.extend(q)
a.extend(r)
a.sort()
a.reverse()
b=q[:]
b.extend(r)
b.sort()
b.reverse()
c=p[:]
c.extend(r)
c.sort()
c.reverse()
red=0
green=0
sum=0
sum1=0
sum2=0
d=0
for i in range(X+Y):
  if(a[i] in p):
    red+=1
  elif(a[i] in q):
    green+=1
  d+=a[i]
 
  if(i<X):
      sum1+=p[i]
      sum2+=c[i]
  if(i<Y):
      sum1+=b[i]
      sum2+=q[i]
    
if(red<=X and green<=Y):
  print(d)
elif(red>X):
  print(sum1)
elif(green>Y):
  print(sum2)

### FIXED CODE ###

N,X,Y=map(int,input().split())

k=[0]*(N-1)
for i in range(N):
  for j in range(i+1,N):
    k[min(j-i,abs(j+1-Y)+1+abs(i+1-X))-1]+=1
    
for i in range(N-1):
  print(k[i])
INF = 1*((10**9)*5000 + 1)
n, k = map(int, input().split())
P = [*map(lambda x: int(x)-1, input().split())]
C = [*map(int, input().split())]

# print(n,k)
# print(P)
# print(C,end='\n\n')

vis = [False]*(n+1)
def dfs(i, c, sum_c=0):
    if vis[i]: return c, sum_c
    vis[i] = True
    c.append(C[i])
    sum_c += C[i]
    ret = dfs(P[i], c, sum_c)
    # vis[i] = False
    return ret

lst_costs = []
for i in range(n):
    costs, lp_c = dfs(i, [])
    if len(costs) == 0: continue
    lst_costs.append((costs,lp_c))

def max_calc(costs, st, num):
    len_c = len(costs)
    max_c = -INF
    sum_c = 0
    for d in range(num):
        i = (st + d) % len_c
        x = costs[i]
        sum_c += x
        max_c = max(max_c, sum_c)
    return max_c

score = -INF
for costs, lp_c in lst_costs:
    # print(costs, lp_c)
    len_c = len(costs)
    cnt, remain = divmod(k, len_c)
    for st in range(len_c):
        cost = -INF
        if lp_c <= 0:
            max_c = max_calc(costs, st, len_c)
            cost = max_c
            # print('1. cost',cost)

        else: # lp_c > 0:
            if cnt == 0:
                max_c = max_calc(costs, st, min(len_c, k))
                cost = max_c
                # print('2. cost',cost)
            else: # cnt > 0
                max_c = max_calc(costs, st, len_c + remain)
                cost = lp_c * (cnt-1)
                cost = max(cost, cost + max_c)
                # print('3. cost',cost)
        score = max({score, cost})
print(score)


### FIXED CODE ###

n, k = map(int, input().split())
P = [*map(lambda x: int(x)-1, input().split())]
C = [*map(int, input().split())]

INF = 10**18
max_score = -INF
for st in range(n):
    lc = 0 # lap count
    lap_sc = 0 # lap score
    nx = st
    while True:
        lc += 1
        lap_sc += C[nx]
        nx = P[nx]
        if nx == st: break

    sum_sc = 0
    kc = 0
    while True:
        kc += 1
        if k < kc: break

        sum_sc += C[nx]
        score = sum_sc + max(0, lap_sc) * ((k - kc) // lc)
        max_score = max(max_score, score)

        nx = P[nx]
        if nx == st: break

print(max_score)

# print('===')
# print(n,k)
# print(P)
# print(C,end='\n\n')
import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

N, M = map(int, input().split())
S = input()
T = input()
L = lcm(N , M)
x = [0] * L
for i in range(N):
    idx = i * (L // N)
    x[idx] = S[i]
for i in range(M):
    idx = i * (L // M)
    if x[idx] != 0 and x[idx] != T[i]:
        print(-1)
        exit()
print(L)


### FIXED CODE ###

import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

N, M = map(int, input().split())
S = input()
T = input()
L = lcm(N , M)
x = {}
for i in range(N):
    idx = i * (L // N)
    x[idx] = S[i]
for i in range(M):
    idx = i * (L // M)
    if idx in x and x[idx] != T[i]:
        print(-1)
        exit()
print(L)
N, M = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ar = [list(map(int, input().split())) for _ in range(M)]
ar.sort(key=lambda x: x[1], reverse=True)
p = 0
for b, c in ar:
    if c <= a[p]:
        break
    for i in range(b):
        if p >= N:
            break
        a[p] = max(a[p], c)
        p += 1
print(sum(a))

### FIXED CODE ###

N, M = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ar = [list(map(int, input().split())) for _ in range(M)]
ar.sort(key=lambda x: x[1], reverse=True)
p = 0
for b, c in ar:
    if p >= N or c <= a[p]:
        break
    for i in range(b):
        if p >= N:
            break
        a[p] = max(a[p], c)
        p += 1
print(sum(a))
n1, n2 = [int(i) for i in input().split()]
n3 = [int(i) for i in input().split()]

n3.sort(reverse = True)

c1 = 0
while True:
    n3[0] = n3[0] // 2
    c1 += 1
    if c1 >= n2:
        break
    t2 = 1
    while len(n3) != 1:
        if n3[t2] >= n3[0]:
            n3[t2] = n3[t2] // 2
            t2 += 1
            c1 += 1
            if c1 >= n2:
                break
        else:
            break

    if c1 >= n2:
        break

    n3.sort(reverse = True)


r1 = 0
for i2 in range(n1):
    r1 += n3[i2]

print(r1)

### FIXED CODE ###

n1, n2 = [int(i) for i in input().split()]
n3 = [int(i) for i in input().split()]

n3.sort(reverse = True)

c1 = 0
while True:
    n3[0] = n3[0] // 2
    c1 += 1
    if c1 >= n2:
        break
    t2 = 1
    while len(n3) != 1:
        if n3[t2] >= n3[0]:
            n3[t2] = n3[t2] // 2
            t2 += 1
            c1 += 1
            if c1 >= n2 or t2 >= len(n3):
                break
        else:
            break

    if c1 >= n2:
        break

    n3.sort(reverse = True)

r1 = 0
for i2 in range(n1):
    r1 += n3[i2]

print(r1)
h,w=map(int,input().split())
if (h*w)%2=1:
    print((h*w+1)//2)
else:
    print((h*w)//a2)

### FIXED CODE ###

h,w=map(int,input().split())
if (h-1)*(w-1)==0:
  print(1)
else:
  print(-(-h*w//2))