Harryxun/stf_run huggingface dataset:
def main():

    n = int(input())
    adj = [[0 for i in range(n)] for j in range(n)]

    for i in range(n):
	tmp = list(map(int, input().split()))
	u = tmp[0]
	u = u -1
	k = tmp[1]
	v = tmp[2:]
	for j in range(k):
            adj[u][v[j]-1] = 1

    for i in range(n):
	print(" ".join(list(map(str, adj[i]))))

    for i in adj:
	print(*i)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():

    n = int(input())
    adj = [[0 for i in range(n)] for j in range(n)]

    for i in range(n):
        tmp = list(map(int, input().split()))
        u = tmp[0]
        u = u -1
        k = tmp[1]
        v = tmp[2:]
        for j in range(k):
            adj[u][v[j]-1] = 1

    for i in adj:
        print(*i)


if __name__ == "__main__":
    main()
import collections
s = input()
ls = len(s)
if ls ==2 and s[0]=!s[1]:
    print(-1,-1)
elif ls ==2 and s[0]==s[1]:
    print(1,2)
for i in range(2,ls):
    tmp = collections.Counter(s[i-2:i+1])
    if len(tmp.keys())<=2:
        print(i-1,i+1)
        exit()
print(-1,-1)

### FIXED CODE ###

import collections
s = input()
ls = len(s)
if ls ==2 and s[0]!=s[1]:
    print(-1,-1)
    exit()
elif ls ==2 and s[0]==s[1]:
    print(1,2)
    exit()
for i in range(2,ls):
    tmp = collections.Counter(s[i-2:i+1])
    if len(tmp.keys())<=2:
        print(i-1,i+1)
        exit()
print(-1,-1)
S=input()

if(S[1]==S[2]==S[3]):
    print("No")
else:
    print("Yes")
    

### FIXED CODE ###

S=input()

if(S[0]==S[1]==S[2]):
    print("No")
else:
    print("Yes")
X, A = map(int, input().split)
print(0 if X < A else 10)

### FIXED CODE ###

X, A = map(int, input().split())
print(0 if X < A else 10)
n = int(input())
A = list(map(int,input().split()))
A.sort()
ans = []

# 全て正
if min(A)>0:
    print(sum(A)-2*A[0])
    for i in range(n):
        if i==0:
            x = A[i]
        elif i==n-1:
            print(A[i], x)
        else:
            print(x, A[i])
            x -= A[i]

# 全て負
elif max(A)<=0:
    A = A[::-1]
    print(sum(A)*(-1) + 2*A[0])
    for i in range(n):
        if i==0:
            x = A[i]
        elif i==n-1:
            print(A[i], x)
        else:
            print(x, A[i])
            x -= A[i]

# 正負
else:
    m,p = [], []
    for a in A:
        if a<0:
            m.append(a)
        else:
            p.append(a)
    print(sum(p)-sum(m))
    m.sort()
    p.sort()
    x = m[0]
    for i in range(len(p)-1):
        print(x, p[i])
        x -= p[i]
    else:
        print(p[-1], x)
        x = p[-1] - x
        
    for j in range(1, len(m)):
        print(x, m[j])
        x -= m[j]

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
A.sort()
ans = []

# 全て正
if min(A)>=0:
    print(sum(A)-2*A[0])
    for i in range(n):
        if i==0:
            x = A[i]
        elif i==n-1:
            print(A[i], x)
        else:
            print(x, A[i])
            x -= A[i]

# 全て負
elif max(A)<=0:
    A = A[::-1]
    print(sum(A)*(-1)+2*A[0])
    for i in range(n):
        if i==0:
            x = A[i]
        else:
            print(x, A[i])
            x -= A[i]

# 正負
else:
    m,p = [], []
    for a in A:
        if a<0:
            m.append(a)
        else:
            p.append(a)
    print(sum(p)-sum(m))
    m.sort()
    p.sort()
    x = m[0]
    for i in range(len(p)-1):
        print(x, p[i])
        x -= p[i]
    else:
        print(p[-1], x)
        x = p[-1] - x
        
    for j in range(1, len(m)):
        print(x, m[j])
        x -= m[j]
N = int(input())
str = ''

while(N != 0):
    if N % 2:
        N -= 1
        N //= -2
        str += '1'
    else:
        N //= -2
        str += '0'
        
if str = '':
    print(0)
else:
    print(str[::-1])


### FIXED CODE ###

N = int(input())
str = ''

while(N != 0):
    if N % 2:
        N -= 1
        N //= -2
        str += '1'
    else:
        N //= -2
        str += '0'

if str == '':
    print(0)
else:
    print(str[::-1])
n=input()
l=list()
q=0
for k in range(n):
	st=input()
    l.append(st)
for i in range(n)[:-1]:
	f=l[i]
	for s in range(n)[i+1:]:
		a=[f[k] for k in range(10)]
        g=l[s]
        b=[g[c] for c in range(10)]
        q +=1 if sorted(a)==sorted(b)
print(q)

### FIXED CODE ###

from collections import Counter as co
from operator import mul
from functools import reduce

def combinations_count(n, r):
  r = min(r, n - r)
  numer = reduce(mul, range(n, n - r, -1), 1)
  denom = reduce(mul, range(1, r + 1), 1)
  return numer//denom


n=int(input())
a=0
l=[''.join(list(map(str,sum(sorted(list(map(list,co(input()).items()))),[])))) for i in range(n)]
for d,s in co(l).items():
  if s>=2:a+=combinations_count(s, 2)
print(a)
import sys

a = []
b = []
for line in sys.stdin:
    a.append(int(line))
    b.append(int(line))

del a[0]
del a[len(a)-1]
del b[0]
del b[0]

sub - -100000000
for i in range(len(a)):
    for j in range(len(b)):
        if j >= i:
            if sub <= b[j]-a[i]:
                sub = b[j]-a[i]
print(sub)


### FIXED CODE ###

import sys

a = []
b = []
for line in sys.stdin:
    a.append(int(line))
    b.append(int(line))

del a[0]
del a[len(a)-1]
del b[0]
del b[0]

maxv = -1000000000
minv = a[0]
for i in range(len(a)):
    maxv = max(maxv,b[i]-minv)
    minv = min(minv,b[i])
print(maxv)
x = int(sys.argv[1])

print(x*x*x)

### FIXED CODE ###

x = int(input())

print(x*x*x)
import sys

N,M, K = map(int,input().split())
AB = [list(map(int,input().split())) for i in range(M)]
CD = [list(map(int,input().split())) for i in range(K)]


#xの木の根を求める
def root(x,li): 
    if li[x] == x:
        return x
    else:
        li[x] = root(li[x],li)
        return li[x]

#xとyが同じ集合に属するかの判定
def find(x,y,li):
    return root(x,li) == root(y,li)

#xとｙを併合
def union(x,y,li):
    x = root(x,li)
    y = root(y,li)
    if x==y:
        return
    else:
        li[x] = y

li1 = [i for i in range(N)]
li2 = [i for i in range(N)]

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    union(a-1,b-1,li1)
# for i in range(K):
#     c = CD[i][0]
#     d = CD[i][1]
#     union(c-1,d-1,li2)

mm = [0 for i in range(max(li1))]
for i in range(N):
    m = root(i,li1)
    mm[m-1] += 1

# print(li1)
# print(mm)
ans = [mm[li1[i]-1]-1 for i in range(N)]
# print(ans)
sys.exit()
for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    ans[a-1] -= 1
    ans[b-1] -= 1


for i in range(K):
    c = CD[i][0]
    d = CD[i][1]
    if find(c-1,d-1,li1):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(*ans)





### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

N,M, K = map(int,input().split())
AB = [list(map(int,input().split())) for i in range(M)]
CD = [list(map(int,input().split())) for i in range(K)]


#xの木の根を求める
def root(x,li): 
    if li[x] == x:
        return x
    else:
        li[x] = root(li[x],li)
        return li[x]

#xとyが同じ集合に属するかの判定
def find(x,y,li):
    return root(x,li) == root(y,li)

#xとｙを併合
def union(x,y,li):
    x = root(x,li)
    y = root(y,li)
    if x==y:
        return
    else:
        li[x]=y

li1 = [i for i in range(N)]
li2 = [i for i in range(N)]

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    # print(str(i)+" ",end="")
    union(min(a-1,b-1),max(a-1,b-1),li1)
# for i in range(K):
#     c = CD[i][0]
#     d = CD[i][1]
#     union(c-1,d-1,li2)

mm = [0 for i in range(max(li1)+1)]
for i in range(N):
    m = root(i,li1)
    mm[m] += 1

# print(li1)
# print(mm)
ans = [mm[li1[i]]-1 for i in range(N)]
# print(ans)

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    ans[a-1] -= 1
    ans[b-1] -= 1


for i in range(K):
    c = CD[i][0]
    d = CD[i][1]
    if find(c-1,d-1,li1):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(*ans)
N=int(input())
L=list(map(int,input().split()))
A=1
for i in range(N):
  A=A*L[i]
  if 10**18<A:
print(-1)
  exit()
else:
  print(A)

### FIXED CODE ###

N=int(input())
L=list(map(int,input().split()))
A=1
if 0 in L:
  print(0)
  exit()
for i in range(N):
  A=A*L[i]
  if 10**18<A:
    print(-1)
    exit()
print(A)
N=int(input())
AB = [tuple(map(int,input().spilt())) for i in range(N)]
AB.sort(key = lambda x:x[1])
curtime = 0
clear = True
for a,b in range(AB):
    if curtime > b:
        clear = False
        break
    curtime += a
if clear:print("Yes")
else:print("No")

### FIXED CODE ###

N=int(input())
AB = [[int(i) for i in input().split()] for j in range(N)]
ABDeadStart = [[A,B,B-A] for A,B in AB]#所要時間、初めてないと駄目な時間
MaxShoyou = sum([a for a,b,kaisi in ABDeadStart])
ABDeadStart.sort(key = lambda x:x[2]-MaxShoyou+x[0])
curtime = 0
NO =0
for a,b,ds in ABDeadStart:
    if curtime <= ds:
        curtime += a
    else:
        NO =True
        break
if NO :print("No")
else:print("Yes")
t = list(input())
for i in len(t):
  if t[i]=='?':
    if i==0:
      t[i]='?'
    if t[i-1]=='D':
      t[i]='P'
    else:
      t[i]='D'
      
print(t)

### FIXED CODE ###

t = list(input())
for i in range(len(t)):
  if t[i]=='?':
    if i==0:
      t[i]='?'
    if t[i-1]=='P':
      t[i]='D'
    else:
      t[i]='D'
      

print(''.join(t))
N = int(input())
S = input()
S = list(S)


indices_black = list()
for i, c in enumerate(S):
    if c == '#':
        indices_black.append(i)

count_white = dict()
count = 0
for i, c in enumerate(S[::-1]):
    if c == '.':
        count += 1
    count_white[N - i - 1] = count


def get_answer(S):
    # most left
    if len(indices_black) == 0:
        return 0

    idx = indices_black.pop(0)
    if count_white[idx] == 0:
        return 0
    # count white: turn all white -> black
    ans_w = count_white[idx]

    # turn most left black -> white
    S[idx] = '.'
    ans_b = get_answer(S) + 1
    return min(ans_w, ans_b)


print(get_answer(S))

### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)


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


indices_black = list()
for i, c in enumerate(S):
    if c == '#':
        indices_black.append(i)

count_white = dict()
count = 0
for i, c in enumerate(S[::-1]):
    if c == '.':
        count += 1
    count_white[N - i - 1] = count


def get_answer(S):
    # most left
    if len(indices_black) == 0:
        return 0

    idx = indices_black.pop(0)
    if count_white[idx] == 0:
        return 0
    # count white: turn all white -> black
    ans_w = count_white[idx]

    # turn most left black -> white
    S[idx] = '.'
    ans_b = get_answer(S) + 1
    return min(ans_w, ans_b)


print(get_answer(S))
n = int(input())
nums = [[0,0,0]]
ans = False

for v in range(n):
    t, x, y = map(int,input().split())
    nums.append([t,x,y])

# print(nums)
# print(nums[1][1])

for x in range(n+1):
    p = nums[x+1][0] - nums[x][0]
    px = nums[x+1][1] - nums[x][1]
    py = nums[x+1][2] - nums[x][2]
    ps = px + py
    # print(p,px,py,ps)

    for w in range(p+1):
        pp = w
        mp = p - pp
        # print(pp,mp)
        if pp-mp==ps:
            ans = True

if ans:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n = int(input())
nums = [[0,0,0]]
ans = []

for v in range(n):
    t, x, y = map(int,input().split())
    nums.append([t,x,y])

# print(nums)
# print(nums[1][1])

for x in range(n):
    p = nums[x+1][0] - nums[x][0]
    px = nums[x+1][1] - nums[x][1]
    py = nums[x+1][2] - nums[x][2]
    ps = px + py
    # print(p,px,py,ps)

    for w in range(p+1):
        pp = w
        mp = p - pp
        # print(pp,mp)
        if pp-mp==ps:
            ans.append(1)
        else:
            ans.append(0)

    
sum = 0 
for num in ans:
    sum = sum + num


if sum==n:
    print('Yes')
else:
    print('No')
print(input() + input())

### FIXED CODE ###

s, t = input().split()
print(t + s)
X, A, B = map(int, input().split())

if min(abs(X - A) < abs(X - B)):
    print ('A')
else:
    print ('B')

### FIXED CODE ###

x, a, b = map(int, input().split())
if abs(x-a) < abs(x-b):
  print ('A')
else:
  print ('B')
n, m, c = map(int, input().split())
b = list(map(int, input().split()))
ans = 0
for _ in range(n):
    a = list(map(int, input().split()))

    if a[0] * b[0] + a[1] * b[1] + a[2] * b[2] + c > 0:
         ans += 1
print(ans)


### FIXED CODE ###

n, m, c = map(int, input().split())
b = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
for ai in a:
    absum = 0
    for i in range(m):
        absum += ai[i] * b[i]
    if absum + c > 0:
        ans += 1
print(ans)
s,w=map(int(),input().split())

if s>w:
  return "safe"
else:
  return "unsafe"

### FIXED CODE ###

s,w=map(int,input().split())
 
if s>w:
	print("safe")
else:
	print("unsafe")
S=str(input())

print(S[0]+(S.count(S)-2)+S[-1])

### FIXED CODE ###

S=str(input())
size=len(S)

print(S[0]+str(int(size)-2)+S[-1])
N = int(input())

A = []
for i in range(20):
    if 6**i<=N:
        A.append(6**i)
for i in range(1,20):
    if 9**i<=N:
        A.append(9**i)
AA = sorted(A,reverse=True)
        
INF = float("inf")
dp=[INF]*(N)
dp[0]=1

for i in range(N):
    for j in AA:
        if i>=j:
        dp[i]=min(dp[i-j]+1,dp[i])
    
#print(dp)
print(dp[-1])

### FIXED CODE ###

N = int(input())

A = []
for i in range(20):
    if 6**i<=N:
        A.append(6**i)
for i in range(1,20):
    if 9**i<=N:
        A.append(9**i)
AA = sorted(A,reverse=True)
#print(AA)
        
INF = float("inf")
dp=[INF]*(N+1)
dp[0]=0

for i in range(N+1):
    for j in AA:
        if i>=j:
            dp[i]=min(dp[i-j]+1,dp[i])
        else:
            dp[i]=dp[i]
    
#print(dp)
print(dp[-1])
import collections
n=int(input())
arr=input().split(" ")
arr_s=set(arr)
a=0
arr_e=[0 for i in range(int(n/2))]
arr_o=[0 for i in range(int(n/2))]
for i in range(int(n/2)):
    arr_e[i]=arr[a]
    arr_o[i]=arr[a+1]
    a+=2
ce=collections.Counter(arr_e).most_common()
co=collections.Counter(arr_o).most_common()
if len(arr_s)==1:
    print(int(n/2))
else:
    if ce[0][0]!=co[0][0]:
        print(n-ce[0][1]-co[0][1])
    else:
        print(n-max(ce[0][1]+co[1][1],ce[1][1]+co[0][1]))

### FIXED CODE ###

num=input()
num_str=list(num)
lengh=len(num_str)
tmp=num_str
for i in range(lengh):
    if num_str[i]=="1":
        tmp[i]="9"
    elif num_str[i]=="9":
        tmp[i]="1"
ans="".join(tmp)
print(ans)
D = int(input())
T = int(input())
S = int(input())

res = S*T
if(res >= D):
    print("Yes")
else:
    print("No")


### FIXED CODE ###

D, T, S = map(int,input().split())

if(D/S <= T):
    print("Yes")
else:
    print("No")
import queue
h,w,n = map(int,input().split())
factrys = [None] * (n + 1)
ss = ["X" * (w + 2)]
for i in range(h):
  s = "X" + input() + "X"
  if "S" in s:
    factrys[0] = (i + 1, s.index("S"))
  for j in range(1,n + 1):
    if str(j) in s:
      factrys[j] = (i + 1, s.index(str(j)))
  ss.append(s)
ss.append("X" * (w + 2))
mp = []
que = queue.Queue()
def bfs(i):
  while True:
    (x,y) = que.get()
  #  print(i,x,y)
  #  print(mp[x][y])
    if (x,y) == factrys[i + 1]:
      return mp[x][y]
    count = mp[x][y]
    if ss[x + 1][y] != "X" and mp[x + 1][y] is None:
      mp[x + 1][y] = count + 1
      que.put((x + 1, y))
    if ss[x - 1][y] != "X" and mp[x - 1][y] is None:
      mp[x - 1][y] = count + 1
      que.put((x - 1, y))
    if ss[x][y + 1] != "X" and mp[x][y + 1] is None:
      mp[x][y + 1] = count + 1
      que.put((x, y + 1))
    if ss[x][y - 1] != "X" and mp[x][y - 1] is None:
      mp[x][y - 1] = count + 1
      que.put((x, y - 1))

def bfs_(i):
  for count in range(1000000):
    sz = que.qsize()
    for loop in range(sz):
      (x,y) = que.get()
      if ss[x][y] == "X" or not mp[x][y] is None:
        continue
      if (x,y) == factrys[i + 1]:
        return count
      mp[x][y] = count
      que.put((x + 1, y))
      que.put((x - 1, y))
      que.put((x, y - 1))
      que.put((x, y + 1))

ans = 0
for i in range(n):
  mp = [[None] * (h + 2) for j in range(w + 2)]
  x,y = factrys[i]
  que = queue.Queue()
  mp[x][y] = 0
  que.put((x,y))
  ans += (bfs(i))
print(ans)


### FIXED CODE ###

from collections import deque

def main():
  h, w, n = map(int, input().split())
  mp = ["X" + input() + "X" for _ in range(h)]
  mp.insert(0, "X" * (w + 2))
  mp.append("X" * (w + 2))
  
  poss = [None] * (n + 1)
  for y in range(1, h + 1):
    for x in range(1, w + 1):
      if mp[y][x] == "S":
        poss[0] = (x, y)
      elif "1" <= mp[y][x] <= "9":
        poss[int(mp[y][x])] = (x, y)
  
  ans = 0
  vec = ((1, 0), (0, -1), (-1, 0), (0, 1))
  for i in range(n):
    sx, sy = poss[i]
    gx, gy = poss[i + 1]
    used = [[False] * (w + 2) for _ in range(h + 2)]
    used[sy][sx] = True
    que = deque()
    push = que.append
    pop = que.popleft
    push((0, sx, sy))
    while que:
      cnt, x, y = pop()
      if (x, y) == (gx, gy):
        ans += cnt
        break
      
      for dx, dy in vec:
        nx, ny = x + dx, y + dy
        if used[ny][nx] or mp[ny][nx] == "X":continue
        used[ny][nx] = True
        push((cnt + 1, nx, ny))
  
  print(ans)

main()
import collections
n = int(input())
v = list(map(int, input().split()))

count = 0
v1 = []
v2 = []
while count < n:
  v1.append(v[count])
  v2.append(v[count + 1])
  count += 2

c1 = collections.Counter(v1)
c2 = collections.Counter(v2)

num1, count1 = c1.most_common()[0]
num2, count2 = c2.most_common()[0]

if num1 != num2:
  min_count = (n // 2 - count1) + (n // 2 - count2)
elif count1 == count2 and count1 == n // 2:
  min_count = (n // 2)
else:
  if count1 == count2:
    for i in range(min(len(c1.most_common()), c2.most_common())):
        a = i + 1
        if c1.most_common()[a][a] == c2.most_common()[a][a]:
            continue
        if c1.most_common()[a][a] > c2.most_common()[a][a]:
            num2, count2 = c2.most_common()[a]
            break
        else:
            num1, count1 = c1.most_common()[a]
            break
    min_count = (n // 2 - count1) + (n // 2 - count2)
  else:
    num3, count3 = c1.most_common()[1]
    num4, count4 = c2.most_common()[1]
    a = (n // 2 - count1) + (n // 2 -count4)
    b = (n // 2 - count2) + (n // 2 -count3)
    min_count = min(a,b)
print(min_count)

### FIXED CODE ###

import collections
n = int(input())
v = list(map(int, input().split()))

count = 0
v1 = []
v2 = []
while count < n:
  v1.append(v[count])
  v2.append(v[count + 1])
  count += 2

c1 = collections.Counter(v1)
c2 = collections.Counter(v2)

num1, count1 = c1.most_common()[0]
num2, count2 = c2.most_common()[0]

if num1 != num2:
  min_count = (n // 2 - count1) + (n // 2 - count2)
elif count1 == count2 and count1 == n // 2:
  min_count = (n // 2)
else:
  if len(c1.most_common()) > 1 and len(c2.most_common()):
    num3, count3 = c1.most_common()[1]
    num4, count4 = c2.most_common()[1]
    a = (n // 2 - count1) + (n // 2 -count4)
    b = (n // 2 - count2) + (n // 2 -count3)
    min_count = min(a,b)
  else:
    if count1 > count2:
      num2, count2 = c2.most_common()[1]
      min_count = (n // 2 - count1) + (n // 2 - count2)
    else:
      num1, count1 = c1.most_common()[1]
      min_count = (n // 2 - count2) + (n // 2 - count1)
print(min_count)
n=int(input())
import bisect
import itertools
ans=[]
num=[]
for i in range(3,l+1):
    m=list(itertools.product(x, repeat=i))
    num.extend(m)
for i in range(len(num)):
    y=num[i]
    if '3' in y and '5' in y and '7' in y:
        number=''
        for j in range(len(y)):
            number+=y[j]
        ans.append(int(number))
ans.sort()
print(bisect.bisect_left(ans, n))

### FIXED CODE ###

n=int(input())
import bisect
import itertools
l=len(str(n))
ans=[]
num=[]
x=['3', '5', '7']
for k in range(3,l+1):
    m=list(itertools.product(x, repeat=k))
    num.extend(m)
for i in range(len(num)):
    y=num[i]
    if '3' in y and '5' in y and '7' in y:
        number=''
        for j in range(len(y)):
            number+=y[j]
        ans.append(int(number))
ans.sort()
print(bisect.bisect_right(ans, n))
#  入力
N = int(input())
B = [int(x) for x in input().split()]

# 初期化
dp = [[0] * (N+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(0,N):

    # 最も嬉しさの高い子供から場所を選択していく
    id = A.index(max(A))
    
    for x in range(0,i+1):
        y = i - x
        
        dp[x+1][y] = max(dp[x+1][y], dp[x][y] + A[id] * (id - x))
        dp[x][y+1] = max(dp[x][y+1], dp[x][y] + A[id] * (((N-1)-y) - id))
        
    A[id] = 0

ans = 0
for i in range(N+1):
    ans = max(ans, dp[i][N-i])
print(ans)

### FIXED CODE ###

#  入力
N = int(input())
A = [int(x) for x in input().split()]

# 初期化
dp = [[0] * (N+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(0,N):

    # 最も嬉しさの高い子供から場所を選択していく
    a = max(A)
    id = A.index(a)
    
    for x in range(0,i+1):
        y = i - x

        d = dp[x][y]
        tmp = d + a * (id - x)
        if dp[x+1][y] < tmp:
        	dp[x+1][y] = tmp
        tmp = d + a * (((N-1)-y) - id)            
        if dp[x][y+1] < tmp:
        	dp[x][y+1] = tmp
        
    A[id] = 0

ans = 0
for i in range(N+1):
    ans = max(ans, dp[i][N-i])
print(ans)
You are not allowed to see this code.


### FIXED CODE ###

i = 1
while True:
  n = int(input())
  if n == 0:
    break
  print("Case ", i, ": ", n, sep = "")
  i = i+1
import math

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


n, a, b, k = map(int, input().split())
count = 0
if k ==0:
    print("0")
    exit()
for i in range(n+1):
    if (k - (i * a)) % b == 0:
        count += int(cmb(n, i) * cmb(n, int((k-i*a)/b)))
print(count%998244353)

### FIXED CODE ###

N,A,B,K = map(int,input().split())
sprime = 998244353 # approx 10**9
A,B = sorted((A,B))
if (A+B) * N < K:
	print(0)
	exit()
 
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
 
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
 
memo = [0] * (N+1)
memo[0] = memo[N] = 1
for i in range(1,N//2+1):
	v = memo[i-1] * (N-i+1) * modinv(i,sprime)
	v = v % sprime
	memo[i] = memo[N-i] = v
 
# max is A*N + B*N
sum = 0
for b in range(N+1):
  a = (K-b*B)//A
  if 0 <= a <= N and a*A+b*B == K:
    sum += memo[a]*memo[b]
    sum %= sprime
 
print(sum)
import math
from functools import reduce

N,X = map(int,input().split(" "))
x = list(map(int,input().split(" ")))
Y = [i-X for i in x]

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

print(gcd_list(Y))

### FIXED CODE ###


from functools import reduce
from fractions import gcd

N,X = map(int,input().split(" "))
x = list(map(int,input().split(" ")))
Y = [abs(i-X) for i in x]

print(reduce(gcd, Y, 0))
def round_up_division(num1, num2):
# 切り上げ除算
  div = -(-num1 // num2)
  return div

def binary_search(search_range, max_num, logs):
  search_min = 1
  search_max = search_range
  # 二分探索
  while True:
    # max_numを超えない最大回数にする
    count_a = 0
    # count_aより1短い長さ
    count_b = 0
    # 最小値と最大値の中間の値を出す
    half_num = (search_min + search_max - 1) // 2 + 1
    for i in range(logs):
      # 木を切る回数は(⌈(木の長さ)//(切りたい長さ)⌉-1)回
      count_a += round_up_division(A[i], half_num) - 1
      count_b += round_up_division(A[i], half_num - 1) - 1
    if count_a <= K and count_b > K:
      # count_aが最大になれば終了
      return half_num
      break
    elif count_b <= K:
      # 少なければ短い半分で探索
      search_max = half_num - 1
    else:
      # 多ければ長い半分で探索
      search_min = round_up_division(search_min + search_max, 2) + 1



N, K = map(int, input().split())
A = list(map(int, input().split()))
length_max = binary_search(max(A), K, N)
print(length_max)

### FIXED CODE ###

def round_up_division(num1, num2):
# 切り上げ除算
  div = -(-num1 // num2)
  return div

def binary_search(search_range, max_num, logs):
  search_min = 1
  search_max = search_range
  # 二分探索
  while True:
    # max_numを超えない最大回数にする
    count_a = 0
    # count_aより1短い長さ
    count_b = 0
    # 最小値と最大値の中間の値を出す
    half_num = (search_min + search_max - 1) // 2 + 1
    for i in range(logs):
      # 木を切る回数は(⌈(木の長さ)//(切りたい長さ)⌉-1)回
      count_a += round_up_division(A[i], half_num) - 1
      if half_num != 1:
        count_b += round_up_division(A[i], half_num - 1) - 1
    if count_a > K:
      # 多ければ長い半分で探索
      search_min = round_up_division(search_min + search_max, 2)
    elif half_num != 1 and count_b <= K:
      # 少なければ短い半分で探索
      search_max = half_num - 1
    else:
      # count_aが最大になれば終了
      return half_num
      break

N, K = map(int, input().split())
A = list(map(int, input().split()))
length_max = binary_search(max(A), K, N)
print(length_max)