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

import numpy as np

s = input()
p = np.array([0]*13)
p[0] = 1

for si in range(len(s)):
  a = np.array([0]*13)
  if s[si] == '?':
    for j in range(10):
      for i in range(13):
        a[(i*10+j)%13] += p[i]
  else:
    c = int(s[si])
    for i in range(13):
      a[(i*10+c)%13] += p[i]
  for i in range(13):
    p = np.mod(a,1000000007)
print(p[5])

### FIXED CODE ###

import numpy as np

s = input()
p = np.array([0]*13)
p[0] = 1

amari = [[0]*13 for _ in range(13)]
for j in range(10):
  for i in range(13):
    amari[i][(i*10+j)%13] += 1
M = np.array(amari)

for si in range(len(s)):
  a = np.array([0]*13)
  if s[si] == '?':
    a = np.dot(p,M)
  else:
    c = int(s[si])
    for i in range(13):
      a[(i*10+c)%13] += p[i]
  p = np.mod(a,1000000007)
print(p[5])
### BUGGY CODE ###

import numpy as np

n,m = map(int, input().split())

amari=m % n
x=int((m-amari)/n)

aaa=np.mod(m,range(1,x+1))
#print(aaa)
index=np.where(aaa==0)
print(index[0][-1]+1)


### FIXED CODE ###

import math

n,m = map(int, input().split())

x=int(math.sqrt(m))

ans=1
for i in range(1,x+1):
  if m%i==0:
    if i*n<=m:
      ans=max(ans,i)
    if int(m/i)*n<=m:
      ans=max(ans,int(m/i))
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, (input() for i in range(N))))
for i in range(N):

  print(max(A[:i]+A[i+1:]))

### FIXED CODE ###

N = int(input())
A = list(map(int, (input() for i in range(N))))
B = sorted(A, reverse=True)
a = B[0]
a1 = B[1]


for x in A:  
  if x != a:
    print(a)
  else:
    print(a1)
### BUGGY CODE ###

n=int(input())
from math import sqrt
for k in range(1,n+1):

    ans=0
    for x in range(1,101):
        for y in range(1,101):
            p=k-x**2 - y**2 - x*y
            if p<=0:
                break
            for z in range(1,int(sqrt(p))+1):
                if z*(z+x+y)==p:
                    ans+=1

    print(ans)


### FIXED CODE ###

n=int(input())

ans=[0]*(n+1)

for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            f= x**2 + y**2 + z**2 + x*y + y*z + z*x
            if f<=n:
                ans[f]+=1

for i in range(1,n+1):
    print(ans[i])
### BUGGY CODE ###

import numpy as np
H, W = map(int, input().split())
S = [0]*H
count = np.zeros((H,W,2))

for i in range(H):
  S[i] = input()
  
for i in range(H):
  for j in range(W):
    if S[i][j]=='.':
      if count[i][j][0]==0:
        l = len(S[i][j:].split('#')[0])
        #print(S[i][j:],l)
        count[i,j:j+l,0]=l
      if count[i][j][1]==0:
        m = len(''.join([S[k][j] for k in range(i,H)]).split('#')[0])
        #print(S[i:][j],m)
        count[i:i+m,j,1]=m
      #print(i,j,count)
#print(count)
maxim = 0
for i in range(H):
  for j in range(W):
    maxim = int(max(maxim,np.sum(count[i][j])-1))
print(maxim)

### FIXED CODE ###

#import numpy as np
H, W = map(int, input().split())
S = [0]*H
counth = [[0]*W for _ in range(H)]  
countw = [[0]*W for _ in range(H)]

for i in range(H):
  S[i] = input()
  
for i in range(H):
  for j in range(W):
    if S[i][j]=='.':
      if counth[i][j]==0:
        b=False
        for k in range(j,W):
          if S[i][k]=='#':
            b = True
            break
        if b==False:
          k+=1
        #print(S[i][j:],l)
        for l in range(j,k):
          #print(i,j,l)
          counth[i][l]=k-j
      if countw[i][j]==0:
        b=False
        for k in range(i,H):
          if S[k][j]=='#':
            b=True
            break
        if b==False:
          k+=1
        #print(S[i:][j],m)
        for l in range(i,k):
          #print(i,j,l)
          countw[l][j]=k-i
      #print(i,j,count)
#print(counth,countw)
maxim = 0
for i in range(H):
  for j in range(W):
    maxim = int(max(maxim,counth[i][j]+countw[i][j]-1))
print(maxim)
### BUGGY CODE ###

def main():
    N, K = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    if K >= 42:
        print(' '.join([str(N) for _ in range(N)]))
        return
    for _ in range(K):
        cumsum = [0 for _ in range(N)]
        for i, a in enumerate(A):
            left = max(0, i - a)
            cumsum[left] += 1
            right = i + 1 + a
            if right <= N - 1:
                cumsum[right] -= 1
        for i in range(1, N):
            cumsum[i] += cumsum[i - 1]
        A = cumsum
    print(' '.join(map(str, A)))
 
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N, K = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    if K >= 42:
        print(' '.join([str(N) for _ in range(N)]))
        return
    for _ in range(K):
        cumsum = [0 for _ in range(N)]
        for i, a in enumerate(A):
            left = max(0, i - a)
            cumsum[left] += 1
            right = i + 1 + a
            if right <= N - 1:
                cumsum[right] -= 1
        for i in range(1, N):
            cumsum[i] += cumsum[i - 1]
        A = cumsum
    print(' '.join(map(str, A)))
 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

        )


print(dp[N-1])


### FIXED CODE ###

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

import sys

n=int(input())
ls=list(map(int,input().split()))
ms=[]

#最初の山の値を求める
for i in range(0,10**9,2):
    x=i
    for j in range(n):
        x=(ls[j]-x//2)*2
    if x==0:
        ms.append(i//2)
        break

for i in range(n-1):
    ms.append((ls[i]-ms[-1]//2)*2)
print(*ms)


### FIXED CODE ###

_,a=open(0)
*a,=map(int,a.split())
t=sum(a)-2*sum(a[1::2])
x=[t]
for i in a:
  t=i*2-t
  x+=t,
print(*x[:-1])
### BUGGY CODE ###

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

while cnt < M:
    a = max(A)
    A[A.index(a)] = a//2
    cnt += 1

print(sum(A))

### FIXED CODE ###

import heapq
from math import ceil
n,m = map(int,input().split())
a = [-int(i) for i in input().split()]
heapq.heapify(a)

for i in range(m):
    heapq.heappush(a,ceil(heapq.heappop(a)/2))

print(-sum(a))
### BUGGY CODE ###

import numpy as np
N, K, Q = map(int, input().split(" "))
point_list = np.array([K]*N)

cnt = 1
while Q >= cnt:
  ans = int(input()) -1 
  point_list[ans] = point_list[ans] + 1
  point_list = point_list - 1
  cnt = cnt + 1

# print(point_list)
for i in range(N):
  if point_list[i] > 0:
    print("Yes")
  else:
    print("No")


### FIXED CODE ###

import numpy as np
N, K, Q = map(int, input().split(" "))
point_list = np.array([K-Q]*N)
ans_num_list = [int(input()) for _ in range(Q)]

num_answer_correct = np.array([0]*N)
for i in ans_num_list:
  num_answer_correct[i-1] += 1

point_list = point_list + num_answer_correct
# print(output)

for i in point_list:
  if i > 0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

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

ans = 0
r = 0
for l in range(N):
    tmp = 0
    for r in range(l, N):
        if tmp + A[r] != tmp ^ A[r]:
            break
        tmp += A[r]
        ans += 1

print(ans)

### FIXED CODE ###

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

ans = 0
l = r = 0
total = A[0]
xor = A[0]

while True:
    if xor == total:
        ans += r - l + 1
        r += 1
        if r == N:
            break
        total += A[r]
        xor ^= A[r]
    else:
        total -= A[l]
        xor ^= A[l]
        l += 1

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

inf = 1001001001
n = int(input())
lis = list(map(int, input().split()))
lis.sort()
ans = 0
for i in range(n-1):
    a = lis[i]
    for j in range(i + 1, n):
        b = lis[j]
        nl = lis[j:] + [inf]
        l = 0
        r = n-j
        while r > l+1:
            mid = (l+r) // 2
            if nl[mid] < a + b:
                l = mid
            else:
                r = mid
        ans += l
print(ans)

### FIXED CODE ###

inf = 1001001001
n = int(input())
lis = list(map(int, input().split()))
lis.sort()
lis.append(inf)
ans = 0
for i in range(n-2):
    a = lis[i]
    for j in range(i + 1, n-1):
        b = lis[j]
        l = j
        r = n
        while r > l+1:
            mid = (l+r) // 2
            if lis[mid] < a + b:
                l = mid
            else:
                r = mid
        ans += l - j
print(ans)
### BUGGY CODE ###

OK = 0
NG = 5000000000

mid = (OK+NG) // 2

s = 0
for i in range(mid):
    s += i

X = int(input())

print("Yes" if X >= 30 else "No")

### FIXED CODE ###

X = int(input())

print("Yes" if 30 <= X else "No")
### BUGGY CODE ###

from sys import stdin
import numpy as np
N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
for i in range(M):
    B, C = [int(x) for x in stdin.readline().rstrip().split()]
    A.extend(list(np.zeros(B)+C))
A.sort(reverse= True)
print(int(sum(A[:N])))

### FIXED CODE ###

from sys import stdin
import collections

N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
A = collections.Counter(A)
for i in range(M):
    B, C = [int(x) for x in stdin.readline().rstrip().split()]
    A[C] += B 
A = dict(A)
A = dict(sorted(A.items()))

S = 0
j = -1

A_key = list(A.keys())
A_value = list(A.values())

while True:
    if A_value[j] < N:
        S += A_value[j] * A_key[j]
        N -= A_value[j]
        j -= 1
    else:
        S += N * A_key[j]
        break
print(S)
### BUGGY CODE ###

n,k = (int(x) for x in input().split())
a = [int(x) for x in input().split()]

l = [1]
now = 1
next = a[0]
count = 0
dupl = -1

for i in range(k):
  now = next
  next = a[now-1]
  
  if now in l:
    dupl = now
    break
  else:
    l.append(now)

if(dupl == -1):
  print(now)

else:
  length = len(l)
  for i in range(length):
    if l[0] == dupl:
      break
    else:
      count += 1
      l.remove(l[0])
    
  length = len(l)
  print(l[(k-count)%length])
  

### FIXED CODE ###

n,k = (int(x) for x in input().split())
a = tuple([int(x) for x in input().split()])
 
c = [0] + [-1]*(n)
l = [1]
now = 1
dupl = -1

for i in range(k):
  now = a[now - 1]
  c[now - 1] += 1
   
  if c[now - 1] == 1:
    dupl = now
    break
  else:
    l.append(now)
    
if dupl == -1:
  print(now)
  exit()
       
notloop = l.index(dupl)
length = len(l)-notloop
print(l[(k-notloop)%length+notloop])
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
QS = []

for _ in range(Q):
    l, r = map(int, input().split())
    s = S[l - 1: r]
    print(s.count("AC"))



### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
QS = []

l = [0, 0]
last = S[0]
for i in range(1, len(S)):
    if last == 'A' and S[i] == 'C':
        l.append(l[-1] + 1)
    else:
        l.append(l[-1])
    last = S[i]

for _ in range(Q):
    left, right = map(int, input().split())
    QS.append((left, right))

# print(l)
for left, right in QS:
    ans = l[right] - l[left]
    print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
p=input().split()
P=[int(z) for z in p]
hopes=[(1+a)/2 for a in P]
def goukei(i):
    S=0
    for a in range(i):
        S+=hopes[a]
    return S
numbers=[]
for a in range(N-K+1):
    number=goukei(a+K)-goukei(a)
    numbers.append(number)
print(max(numbers))


### FIXED CODE ###

N,K=map(int,input().split())
p=input().split()
P=[int(z) for z in p]
hopes=[(1+a)/2 for a in P]
S=sum(hopes[:K])
answers=[S]
for a in range(1,N-K+1):
    S=S+hopes[a+K-1]-hopes[a-1]
    answers.append(S)
print(max(answers))
### BUGGY CODE ###

from math import factorial
mod = 10**9+7
def comb(n,k,p):
    if n<0 or k<0 or n<k:
        return 0
    if n==0 or k==0:
        return 1
    a = factorial(n)%p
    b = factorial(k)%p
    c = factorial(n-k)%p
    return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

def power_func(a,b,p):
    if b==0:
        return 1
    if b%2==0:
        d = power_func(a,b//2,p)
        return d*d %p
    if b%2 == 1:
        return (a*power_func(a,b-1,p ))%p

x,y = map(int,input().split())
if (x+y)%3 != 0:
    print(0)
else:
    n = (2*x - y)//3
    m = (2*y - x)//3
    if min(n,m) < 0:
        print(0)
        exit()
    ans = comb(n+m , n , mod)
    print(ans)

### FIXED CODE ###

x,y = map(int,input().split())
mod = 10**9 + 7
if (x+y)%3 != 0:
    print(0)
    exit()
n = (x+y)//3
a = (2 * x - y) // 3
b = (2 * y - x) // 3
if a == 0 or b == 0:
    print(1)
    exit()
if a < 0 or b < 0:
    print(0)
    exit()
MAX = 700000
fac = [1,1] + [0] * MAX     #累積積
finv = [1,1] + [0] * MAX    #modにおける逆元
inv = [0,1] + [0] * MAX     #invの累積積
for i in range(2,MAX):
    fac[i] = fac[i-1] * i % mod
    inv[i] = -inv[mod%i] * (mod//i)%mod
    finv[i] = finv[i-1] * inv[i]%mod


def nCr(n,r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fac[n] * (finv[r] * finv[n-r]%mod)%mod

print(nCr(n,a))
### BUGGY CODE ###


N=int(input().strip())
T=list(map(int,input().split()))
V=list(map(int,input().split()))
# 解説読んだ後
def get_maxspeed(left,right,vmax):
    def maxspeed(t):
        if t<=left:
            return vmax+(left-t)
        elif left< t < right:
            return vmax
        else:
            return vmax+t-right
    return maxspeed
funcs=[]
funcs.append(get_maxspeed(0,0,0))
left=0
for i in range(N):
    funcs.append(get_maxspeed(left,left+T[i],V[i]))
    left+=T[i]
funcs.append(get_maxspeed(left,left,0))
dist=0.0
speed=0
t=0
while t<=left:
    speed2=min(fc(t) for fc in funcs)
    if 0< t:
        dist+=(speed+speed2)*0.5/2
    speed=speed2
    t+=0.5
print(dist)

### FIXED CODE ###

N=int(input().strip())
T=list(map(int,input().split()))
V=list(map(int,input().split()))
vtmax=[0]
tmp=0
Tsum=sum(T)
for t,v in zip(T,V):
    vtmax[-1]=min(tmp,v) #境界は小さい方が制約
    vtmax+=[v]*(t*2)
    tmp=v
vtmax[-1]=0

for i in range(1,2*Tsum):
    vtmax[i]=min(vtmax[i],vtmax[i-1]+0.5)
for i in range(2*Tsum-1,0,-1):
    vtmax[i]=min(vtmax[i],vtmax[i+1]+0.5)
area=0
for i,vt in enumerate(vtmax):
    if i==0:continue
    area+=0.5*(vt+vtmax[i-1])/2
print(area)
### BUGGY CODE ###

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

A = set(x for x in range(1,N+1))
for i in range(M):
  L, R = map(int, input().split())
  A &= {x for x in range(L,R+1)}

print (len(A))


### FIXED CODE ###

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

L = []
R = []
for i in range(M):
  l, r = map(int, input().split())
  L.append(l)
  R.append(r)
print (max(0, min(R)-max(L)+1))
### BUGGY CODE ###

import bisect
A, B, Q = map(int, input().split())

s = [int(input()) for i in range(A)]
t = [int(input()) for i in range(B)]

for i in range(Q):
    x = int(input())
    ret = 2 * 10**10
    a = bisect.bisect_left(s, x)
    tmp = 0
    if a < len(s):
        tmp = abs(s[a] - x)
        ab = bisect.bisect_left(t, s[a])
        if ab < len(t):
            tmp2 = abs(t[ab] - s[a])
            ret = min(ret, tmp + tmp2)

        if ab > 0:
            tmp2 = abs(t[ab - 1] - s[a])
            ret = min(ret, tmp + tmp2)
    if a > 0:
        a -= 1
        tmp = 0
        tmp = abs(s[a] - x)
        ab = bisect.bisect_left(t, s[a])
        if ab < len(t):
            tmp2 = abs(t[ab] - s[a])
            ret = min(ret, tmp + tmp2)

        if ab > 0:
            tmp2 = abs(t[ab - 1] - s[a])
            ret = min(ret, tmp + tmp2)

    b = bisect.bisect_left(t, x)
    tmp = 0
    if b < len(t):
        tmp = abs(t[b] - x)
        ba = bisect.bisect_left(s, t[b])
        if ba < len(s):
            tmp2 = abs(s[ba] - t[b])
            ret = min(ret, tmp + tmp2)
        if ba > 0:
            tmp2 = abs(s[ba - 1] - t[b])
            ret = min(ret, tmp + tmp2)
    if b > 0:
        b -= 1
        tmp = abs(t[b] - x)
        ba = bisect.bisect_left(s, t[b])
        if ba < len(s):
            tmp2 = abs(s[ba] - t[b])
            ret = min(ret, tmp + tmp2)

        if ba > 0:
            tmp2 = abs(s[ba - 1] - t[b])
            ret = min(ret, tmp + tmp2)
    print(ret)


### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
A, B, Q = map(int, input().split())

s = [int(input()) for i in range(A)]
t = [int(input()) for i in range(B)]

for i in range(Q):
    x = int(input())
    ret = 2 * 10**10
    a = bisect.bisect_left(s, x)
    tmp = 0
    if a < len(s):
        tmp = abs(s[a] - x)
        ab = bisect.bisect_left(t, s[a])
        if ab < len(t):
            tmp2 = abs(t[ab] - s[a])
            ret = min(ret, tmp + tmp2)

        if ab > 0:
            tmp2 = abs(t[ab - 1] - s[a])
            ret = min(ret, tmp + tmp2)
    if a > 0:
        a -= 1
        tmp = 0
        tmp = abs(s[a] - x)
        ab = bisect.bisect_left(t, s[a])
        if ab < len(t):
            tmp2 = abs(t[ab] - s[a])
            ret = min(ret, tmp + tmp2)

        if ab > 0:
            tmp2 = abs(t[ab - 1] - s[a])
            ret = min(ret, tmp + tmp2)

    b = bisect.bisect_left(t, x)
    tmp = 0
    if b < len(t):
        tmp = abs(t[b] - x)
        ba = bisect.bisect_left(s, t[b])
        if ba < len(s):
            tmp2 = abs(s[ba] - t[b])
            ret = min(ret, tmp + tmp2)
        if ba > 0:
            tmp2 = abs(s[ba - 1] - t[b])
            ret = min(ret, tmp + tmp2)
    if b > 0:
        b -= 1
        tmp = abs(t[b] - x)
        ba = bisect.bisect_left(s, t[b])
        if ba < len(s):
            tmp2 = abs(s[ba] - t[b])
            ret = min(ret, tmp + tmp2)

        if ba > 0:
            tmp2 = abs(s[ba - 1] - t[b])
            ret = min(ret, tmp + tmp2)
    print(ret)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def calc(a, b):
  if a == 1 or b == 1:
    return 1

  while a != 0 and b != 0:
    if a < b:
      b %= a
    else:
      a %= b

  return a if a != 0 else b


def main():
  input()
  a = list(map(int, input().split()))
  p = [a[0], a[1], calc(a[0], a[1])]

  for v in a[2:]:
    for j in range(len(p) - 1):
      p[j] = calc(p[j], v)

    p.append(calc(p[-1], v))

  print(max(p), flush=True)


if __name__ == '__main__':
  main()



### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def cd(a, b):
  if a == 1 or b == 1:
    return 1

  while a != 0 and b != 0:
    if a < b:
      b %= a
    else:
      a %= b

  return a if a != 0 else b


def main():
  input()
  prevs = list(map(int, input().split()))
  posts = prevs[::-1]

  for i in range(1, len(prevs)):
    prevs[i] = cd(prevs[i - 1], prevs[i])
    posts[i] = cd(posts[i - 1], posts[i])

  posts = posts[::-1]

  gcd = max(prevs[-2], posts[1])

  for i in range(1, len(prevs) - 1):
    gcd = max(cd(prevs[i - 1], posts[i + 1]), gcd)

  print(gcd, flush=True)


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

n, m = map(int, input().split())
ids = [0 for _ in range(n)]
for i in range(m):
  l, r = map(int, input().split())
  for j in range(l-1, r):
    ids[j] += 1

ans = 0
for tmp_id in ids:
  if tmp_id == m:
    ans += 1
print(ans)  

### FIXED CODE ###

n, m = map(int, input().split())

l_tmp = 0
r_tmp = n+1
for i in range(m):
  l, r = map(int, input().split())
  l_tmp = l if l > l_tmp else l_tmp
  r_tmp = r if r < r_tmp else r_tmp

if r_tmp-l_tmp >= 0:
  print(r_tmp-l_tmp+1)
else:
  print(0)
### BUGGY CODE ###

#!/usr/bin/env python3
h,w,k = map(int,input().split())
b =[]
for i in range(h):
    s = input()
    b.append(s)
# 縦の切り方を固定すれば、左から見て貪欲に考えることができる。
# どれかの切り方でK+1　以上1 のマスがあれば、そこで切る
if h == 1:
    print(math.ceil(s//k))
    exit()
# リストで現在のそれぞれのブロックの1の数を持つ

# 列の切断が入ったときに全て0に初期化
# bit 全探索は 2 ** h-1 存在する 
ans = h*w #INF
for i in range(2**(h-1)):
    cnt_white = [0] 
    # ループの中で宣言する
    ans_i = 0
    #前処理として、どこに切れ込みがあるかを見て、リストの構成
    for bit in range(h-1):
        if i >> bit & 1:
            cnt_white.append(0)
            ans_i += 1
    #print("i = ",i,cnt_white)
    c = 0
    while c < w:# 左から貪欲
        r_idx = 0
        last_div = 0
        for r in range(h):
            if b[r][c] == "1":#対応するブロックのcnt+=1
                cnt_white[r_idx] += 1
                #print("col = ",c,cnt_white,r_idx,ans_i)
            if i >> r & 1:#次にブロックが変わるのでidxを増やす
                r_idx += 1
        # 最後の行だけでmax(cnt_white) >= k+1になるときはその切り方では不可能
        if max(cnt_white) >= k+1:
            # 戻らないといけない
            ans_i += 1
            if last_div == w-1:
                ans_i = h*w  #INF
                break
            last_div = c
            c -= 1
            cnt_white = [0]*len(cnt_white)#初期化
            #print("initialize")
        c += 1
    ans = min(ans,ans_i)
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
h,w,k = map(int,input().split())
b =[]
for i in range(h):
    s = input()
    b.append(s)
# 縦の切り方を固定すれば、左から見て貪欲に考えることができる。
# どれかの切り方でK+1　以上1 のマスがあれば、そこで切る
if h == 1:
    print(math.ceil(s//k))
    exit()
# リストで現在のそれぞれのブロックの1の数を持つ

# 列の切断が入ったときに全て0に初期化
# bit 全探索は 2 ** h-1 存在する 
ans = h*w #INF
for i in range(2**(h-1)):
    cnt_white = [0] 
    # ループの中で宣言する
    ans_i = 0
    #前処理として、どこに切れ込みがあるかを見て、リストの構成
    for bit in range(h-1):
        if i >> bit & 1:
            cnt_white.append(0)
            ans_i += 1
    #print("i = ",i,cnt_white)
    c = 0
    last_div = 0
    while c < w:# 左から貪欲
        r_idx = 0
        
        for r in range(h):
            if b[r][c] == "1":#対応するブロックのcnt+=1
                cnt_white[r_idx] += 1
                #print("col = ",c,cnt_white,r_idx,ans_i)
            if i >> r & 1:#次にブロックが変わるのでidxを増やす
                r_idx += 1
        # 1行だけでmax(cnt_white) >= k+1になるときはその切り方では不可能
        if max(cnt_white) >= k+1:
            # 戻らないといけない
            ans_i += 1
            if c == last_div:
                ans_i = h*w  #INF
                break
            last_div = c
            c -= 1
            cnt_white = [0]*len(cnt_white)#初期化
            #print("initialize",last_div)
        c += 1
    ans = min(ans,ans_i)
print(ans)
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()

n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))
a.sort()
f = sorted(f, reverse=True)
cost = []
for i in range(n):
    cost.append(a[i]*f[i])
left = -1
right = max(cost)
def solve(x):
    cnt = 0
    for i in range(n):
        d = cost[i] - x
        if d <= 0:
            continue
        cnt += d//f[i] + int(d % f[i] != 0)
    if cnt <= k:
        return True
    else:
        return False
while right - left > 1:
    mid = (right + left) // 2
    if solve(mid):
        right = mid
    else:
        left = mid
print(right)

### FIXED CODE ###

import numpy as np
N,K = map(int,input().split())
A = np.array(list(map(int,input().split())))
F = np.array(list(map(int,input().split())))
A = np.sort(A)
F = np.sort(F)[::-1]
Asum = A.sum()

def test(x):
    return Asum - np.minimum(A,x//F).sum() <= K

left = -1
right = np.amax(A * F)

while right - left > 1:
    mid = (right + left)//2
    if test(mid) == 1:
        right = mid
    else:
        left = mid
print(right)
### BUGGY CODE ###


# -*- coding: utf-8 -*-
import numpy as np
N=int(input())
As=list(map(int, input().split()))

As=np.array(As)
inds=np.argsort(As)[::-1]
As=As[inds]

ds=np.empty((N+1,N+1),dtype=np.int64)

ds[0][0]=0
for i in range(1,N+1):
    ds[i][0]=ds[i-1][0]+As[i-1]*(inds[i-1]-(i-1))
    ds[0][i]=ds[0][i-1]+As[i-1]*(N-i-inds[i-1])

for xy in range(2,N+1):
    a=As[xy-1]
    i=inds[xy-1]
    for x in range(1,xy):
        y=xy-x
        c1=ds[x-1,y]+a*(i-(x-1))
        c2=ds[x,y-1]+a*(N-y-i)
        ds[x,y]=max(c1,c2)

ans=0
for x in range(0,N+1):
    y=N-x
    c=ds[x,y]
    ans=max(c,ans)
print(ans)
#print(ds)
#print(inds)




### FIXED CODE ###


# -*- coding: utf-8 -*-

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

inds=sorted(range(len(As)), key=lambda k: As[k])[::-1]
#ds=[[0 for j in range(N+1-i)] for i in range(N+1)]

ds=[0]
for xy in range(1,N+1):
    i=inds[xy-1]
    a=As[i]
    nds=[0]*(xy+1)
    nds[-1]=ds[-1]+a*(i-(xy-1))
    nds[0]=ds[0]+a*(N-xy-i)

    for x in range(1,xy):
        y=xy-x
        c1=ds[x-1]+a*abs(i-(x-1))
        c2=ds[x]+a*abs(N-y-i)
        nds[x]=max(c1,c2)
    ds=nds.copy()
    #print(ds)


print(max(ds))
#print(ds)
#print(inds)