Harryxun/stf_run huggingface dataset:
import sys

h,w = [int(i) for i in input().split()]

sys.setrecursionlimit(100000)

s = [['#']*(w+2)] + [['#']+list(input())+['#'] for _ in range(h)] + [['#']*(w+2)]
#print(s)

cost = [[-1 if s[y][x] == '#' else float('inf') for x in range(w+2)] for y in range(h+2)]
cost[1][1] = 0
#print(cost)

move_que = [[1,1]]

def list_flatten(nested_list):
  flat_list = []
  fringe = [nested_list]
  
  while len(fringe) > 0:
    node = fringe.pop(0)
    if isinstance(node, list):
      fringe = node + fringe
    else:
      flat_list.append(node)

  return(flat_list)
      
def move(place):
  y,x = place
  if cost[y+1][x] != -1　or cost[y+1][x] != float('inf'):
      cost[y+1][x] = cost[y][x]+1
      move_que.append([y+1,x])       
      
  if cost[y-1][x] != -1 or cost[y-1][x] != float('inf'):
      cost[y-1][x] = cost[y][x]+1
      move_que.append([y-1,x])
  
  if cost[y][x+1] != -1 or cost[y][x+1] != float('inf'):
      cost[y][x+1] = cost[y][x]+1
      move_que.append([y,x+1])
  
  if cost[y][x-1] != -1 or cost[y][x-1] != float('inf'):
      cost[y][x-1] = cost[y][x]+1
      move_que.append([y,x-1])
  
while len(move_que) != 0:
  move(move_que[0])
  move_que = move_que[1:]

#print(cost)

if cost[h][w] == float('inf'):
  print(-1)
else:
  while_num = list_flatten(s).count('.')
  print(while_num - (cost[h][w]+1))


### FIXED CODE ###

import sys

h,w = [int(i) for i in input().split()]

sys.setrecursionlimit(100000)

s = [['#']*(w+2)] + [['#']+list(input())+['#'] for _ in range(h)] + [['#']*(w+2)]
#print(s)

cost = [[-1 if s[y][x] == '#' else float('inf') for x in range(w+2)] for y in range(h+2)]
cost[1][1] = 0
#print(cost)

def list_flatten(nested_list):
  flat_list = []
  fringe = [nested_list]
  
  while len(fringe) > 0:
    node = fringe.pop(0)
    if isinstance(node, list):
      fringe = node + fringe
    else:
      flat_list.append(node)

  return(flat_list)
      
def move(y,x):
  if cost[y+1][x] != -1:
    if cost[y+1][x] > cost[y][x]+1:
      cost[y+1][x] = cost[y][x]+1
      move(y+1,x)
      
  if cost[y-1][x] != -1:
    if cost[y-1][x] > cost[y][x]+1:
      cost[y-1][x] = cost[y][x]+1
      move(y-1,x)
  
  if cost[y][x+1] != -1:
    if cost[y][x+1] > cost[y][x]+1:
      cost[y][x+1] = cost[y][x]+1
      move(y,x+1)
  
  if cost[y][x-1] != -1:
    if cost[y][x-1] > cost[y][x]+1:
      cost[y][x-1] = cost[y][x]+1
      move(y,x-1)
  

move(1,1)

#print(cost)

if cost[h][w] == float('inf'):
  print(-1)
else:
  while_num = list_flatten(s).count('.')
  print(while_num - (cost[h][w]+1))
n,m=map(int,input().split())
edge=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
depth=[-1 for i in range(n)]
def check(i,h):
    depth[i]=h
    for j in edge[i]:
        if depth[j]==-1:
            check(j,h+1)
        elif depth[j]%2==depth[i]%2:
            return False
    return True
if check(0,0):
    blk=0
    whi=0
    for i in range(n):
        if depth[i]%2==0:
            blk+=1
        else:
            whi+=1
    ret=0
    for i in range(n):
        if depth[i]%2==0:
            ret+=whi-len(edge[i])
        else:
            ret+=blk-len(edge[i])
    print(ret//2)
else:
    print(n*(n-1)//2-m)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
n, m = map(int, input().split())
edge = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)
# -1 → 0,1に塗っていきます
color=[-1 for i in range(n)]
def dfs(pos):
    ret = True
    for i in range(len(edge[pos])):
        to = edge[pos][i]
        if color[to] == -1:
            color[to] = 1 ^ color[pos]
            ret &= dfs(to)
        else:
            ret &= not (color[to]==color[pos])
    return ret

color[0]=0
if dfs(0):
    black, white = 0, 0
    for i in range(n):
        if color[i]==0:
            black += 1
        else:
            white += 1
    print(black*white-m)
else:
    print(n*(n-1)//2-m)
A, B, K = map(int, input().split())
L = list(range(A, B + 1))
if len(L) <= 2 * K:
    for l in L:
        print(l)
else:
    ans = []
    for i in range(K):
        ans.append(L[i])
        ans.append(L[-i])
    for a in ans:
        print(a)


### FIXED CODE ###

A, B, K = map(int, input().split())
L = []

for i in range(K):
    if A + i > B - i:
        break
    else:
        L.append(A + i)
        L.append(B - i)

L = set(L)
L = sorted(L)

for l in L:
    print(l)
a = int(input())
b = int(input())
c = int(input())
x = int(input())
ans = 0

for i in range(len(a)):
  for j in range(len(b)):
    for k in range(len(c)):
      if a+b+c == x:
        ans = ans+1
        
print(ans)

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
x = int(input())
ans = 0

for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):
      if 500*i+100*j+50*k == x:
        ans = ans+1
        
print(ans)
def main():
    n, m = map(int, input().split())
    s = [0] * n
    c = [0] * n
    for i in range(m):
        s[i], c[i] = map(int, input().split())
    ans = list()
    for i in range(n):
        ans.append(0)
    for i in range(m):
        if n != 1 and s[i] == 1 and c[i] == 0:
            print(-1)
            exit()
        if ans[s[i]-1] == 0 or ans[s[i]-1] == c[i]:
            ans[s[i]-1] = c[i]
        elif ans[s[i]-1] != 0 and ans[s[i]-1] != c[i]:
            print(-1)
            exit()
    if n != 1:
        if ans[0] == 0:
            ans[0] = 1
        print(*ans, sep='')
    else:
        print(*ans, sep='')

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    s = [0] * m
    c = [0] * m
    for i in range(m):
        s[i], c[i] = map(int, input().split())
    ans = list()
    for i in range(n):
        ans.append(0)
    for i in range(m):
        if n != 1 and s[i] == 1 and c[i] == 0:
            print(-1)
            exit()
        if ans[s[i]-1] == 0 or ans[s[i]-1] == c[i]:
            ans[s[i]-1] = c[i]
        elif ans[s[i]-1] != 0 and ans[s[i]-1] != c[i]:
            print(-1)
            exit()
    if n != 1:
        if ans[0] == 0:
            ans[0] = 1
        print(*ans, sep='')
    else:
        print(*ans, sep='')

if __name__ == '__main__':
    main()
n = int(input)

print('Hello World' if n == 1)

if n == 2:
    for _ in range():
        a, b = int(input())

    print(a+b)

### FIXED CODE ###

n = int(input())

if n == 1:
    print('Hello World')

if n == 2:
    a = [int(input()) for _ in range(2)]

    print(sum(a))
a = int(input())
b = int(input())
max1 = max(a,b)
max2 = max(min(a,b),max(a,b)-1)
print(max1 + max2)

### FIXED CODE ###

a,b=map(int, input().split()) 
max1 = max(a,b)
max2 = max(min(a,b), max(a,b)-1)
 
print(max1+max2)
n=int(input())
a=int(input())
b=int(input())
if n==1:
    print('Hello World')
else:
    print(a+b)

### FIXED CODE ###

n=int(input())
if n==1:
    print('Hello World')
else:
    a=int(input())
    b=int(input())
    print(a+b)
n = int(input())
x = list(map(int, input().split()))

sx = sorted(x)
xm = sx[n//2]
xp = sx[n//2+1]

for i in range(n):
  if x[i] <= xm:
    b = xp
  else:
    b = xm
  print(b)


### FIXED CODE ###

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

sortedx = x[:]
sortedx.sort()

for i in range(n):
    #ix = sortedx.index(x[i])
    #print(sortedx)
    #print(ix)
    if x[i] <= sortedx[n//2-1]:
        print(sortedx[n//2])
    else:
        print(sortedx[n//2-1])
W,H,x,y,r = list(map(int,input().split()))
 if 0 <= x - r or x - r < x + r
  print('yes')
 elif 0 <= y - r or y - r <= y + r:
  print('yes')
 else:
  print('no')

### FIXED CODE ###

W, H, x, y, r = list(map(int, input().split()))
print('Yes' if 0 <= x - r <= x + r <= W and 0 <= y - r <= y + r <= H else 'No')
x = map(int, raw_input().split(" "))
 print(x**3)

### FIXED CODE ###

x = raw_input()
print(int(x)**3)
#input
N = int(input())
Tree = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    Tree[a].append(b)
    Tree[b].append(a)

# process
# 距離3の頂点を抽出
pair = []
for i in range(N):
    for j in Tree[i]:
        for k in Tree[j]:
            if k == i:
                continue
            for l in Tree[k]:
                if l == j or i > l:
                    continue
                pair.append((i,l))

# 順列を求める
def getAddNum(x, ans):
    t = 0
    for i in range(N):
        if (x+i)%3 == 0:
            t = i

    l = [x for x in range(t, N, 3)]
    for y in l:
        if not y in ans:
            return y

    return -1

def getMulNum(x, ans):
    l = []
    if x%3 == 0:
        l = [n for n in range(1, N+1)]

    else:
        l = [n*3 for n in range(1, N//3+1)]

    for y in l:
        if not y in ans:
            return y

    return -1

def getNextNum(x, ans):
    for y in range(x+1, N):
        if not y in ans:
            return y
    
ans = [-1 for _ in range(1, N+1)]
n = 1
for a, b in pair:
    a -= 1
    b -= 1
    if ans[a] == -1:
        ans[a] = n
        n = getNextNum(n, ans)
    
    t = getAddNum(ans[a], ans)
    if t > 0:
        ans[b] = t
    else:
        t = getMulNum(ans[a], ans)
        ans[b] = t

for i in range(N):
    if ans[i] == -1:
        ans[i] = n
        n = getNextNum(n, ans)

# output
# print(pair)
print(" ".join(map(str, ans)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
from collections import deque

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

# process
# 頂点を2グループに分類
group = [-1]*N
group[0] = False
def categorize2g(pi, i, g):
    for ci in Edges[i]:
        if ci == pi:
            continue
        group[ci] = not g
        categorize2g(i, ci, not g)

categorize2g(-1, 0, 0)

# 順列を求める
ans = [0]*N
mod0 = [x for x in range(1, N+1) if x%3 == 0]
mod1 = [x for x in range(1, N+1) if x%3 == 1]
mod2 = [x for x in range(1, N+1) if x%3 == 2]
gtnum = sum(group)
if gtnum <= N//3:
    dq = deque(mod1+mod2+mod0)
elif N-gtnum <= N//3:
    dq = deque(mod0+mod1+mod2)
else:
    dq = deque(mod1+mod0+mod2)

if len(ans) == N:
    for i, g in enumerate(group):
        if g:
            ans[i] = dq.pop()
        else:
            ans[i] = dq.popleft()

# output
# print(group)
print(" ".join(map(str, ans)))
n, l = map(int, input().split())

taste_lists = []
for i in range(n):
  taste = l+i-1
  taste_lists.append(taste)

for i in taste_lists:
  if i<0:
    taste_lists[i] = abs(i)

taste_lists.sort()
taste_lists.pop(0)

ans = 0
for i in taste_lists:
  ans += i
  
print(ans)

### FIXED CODE ###

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

taste_lists = list()
for i in range(n):
    taste = l+i
    taste_lists.append(taste)

eat = 0
if taste_lists[0] > 0 and taste_lists[-1] > 0:
    eat = taste_lists[0]
elif taste_lists[0] < 0 and taste_lists[-1] < 0:
    eat = taste_lists[-1]
else:
    eat = 0

taste_lists.remove(eat)
ans = 0
for i in taste_lists:
    ans += i

print(ans)
H,A = map(int,input().split())
answer = H // A
if answer == 0
	answer += 1
print(answer)

### FIXED CODE ###

H,A = map(int,input().split())
answer = H // A + 1
if H % A == 0:
	answer -= 1
print(answer)
from scipy.misc import comb


if __name__ == "__main__":
    n, a, b = map(int, input().split())
    ans=0
    if n == 2:
        if (a == 1 and b == 1) or (a == 2 and b == 1):
            print(0)
    else:
        for i in range(1, int(n // 2)):
            cnt=2
            if i == a or i == b:
                cnt -= 1
            if (n - i) == a or (n - i) == b:
                cnt -= 1
            ans += comb(n,i,exact=True)*cnt
        if n%2==0 and (int(n//2) !=a and int(n//2) != b):
            ans += comb(n,int(n//2),exact=True)
        if n != a and n != b:
            ans += 1
        print(ans % (10 ** 9 + 7))

### FIXED CODE ###

n,a,b=map(int,input().split())
MOD=10**9+7
total=(pow(2,n,MOD)-1)%MOD
na=1
nb=1
atotal=1
btotal=1
for i in range(a):
    na=(na*(n-i))%MOD
for i in range(b):
    nb=(nb*(n-i))%MOD
for i in range(1,a+1):
    atotal=(atotal*i)%MOD
for i in range(1, b + 1):
    btotal = (btotal * i) % MOD
atotal=pow(atotal,MOD-2,MOD)%MOD
btotal=pow(btotal,MOD-2,MOD)%MOD
ans=total%MOD-(na*atotal)%MOD-(nb*btotal)%MOD
print(ans%MOD)
N=int(input())
a=list(map(int,input()))
print(min(a))

### FIXED CODE ###

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

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

a.sort()

ans = 1
for i in range(N):
    ans *= gcd(a[i],i)
    ans %= Mod

print(ans)
import collections
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[]
now=0
for i in range(n+1):
        ans.append(a[now])
        now=a[now]-1
#print(ans)

ans2=collections.Counter(ans)

ac=ans2.most_common()[0][0]
#print(ac)
index=-1
index2=-1

for i in range(len(ans)):
    if ans[i]==ac:
        if index==-1:        
            index=i
        else:
            index2=i
assert(index2 == -1)
#print(index,index2)
#print((k-index-1)%(index2-index))
if k < index:
    print(ans[k])
else:
    print(ans[(k-index-1)%(index2-index)+index])



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n,k = map(int, input().split())
a = list(map(int, input().split()))
adjacent_list = [[] for i in range(n+1)]
for i in range(n):
    adjacent_list[i+1].append(a[i])
finished = set()
route = []
def dfs(node):
    finished.add(node)
    route.append(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)
dfs(1)
if len(route) > k:
    print(route[k])
else:
    index = route.index(adjacent_list[route[-1]][0])
    k -= index
    route = route[index:]
    print(route[k % len(route)])
from fractions import gcd

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

agcd = gcd(*a)

if max(a) > k and k%agcd ==0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

### FIXED CODE ###

from fractions import gcd
from functools import reduce

def gcdd(*numbers):
    return reduce(gcd, numbers)

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

agcd = gcdd(*a)

if max(a) >= k and k%agcd ==0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')
import numpy as np
r = int(input())

return  2 * r * np.pi

### FIXED CODE ###

import numpy as np
r = int(input())

print(2 * r * np.pi)
s = input()
S = int(s)
a = S/(60*60)
b = (S-(int(a))*60*60)/60
c = S-(int(a)*60*60 + int(b)*60)
print(int(a), ":", int(b), ":", int(c)\n)


### FIXED CODE ###

S = int(input())
a = S//(60*60)
b = (S-(a*60*60))//60
c = S-(a*60*60 + b*60)
print(a, ':', b, ':', c, sep='')
a,b,c,d = map(int,input().split())
if a >= 0:
  if d <= 0:
    print(a*d)
  else:
    print(b*d)
    
elif b>0:
  if d<0:
    print(a*c)
  else:
    print(max(a*c,b*d)
else:
  if c>=0:
    print(b*c)
  else:
    print(a*c)

### FIXED CODE ###

a,b,c,d = map(int,input().split())
if a >= 0:
  if d <= 0:
    print(a*d)
  else:
    print(b*d)
    
elif b>0:
  if d<0:
    print(a*c)
  else:
    print(max(a*c,b*d))
else:
  if c>=0:
    print(b*c)
  else:
    print(a*c)
s = []
for i in range(4):
    s.append(int(input()))

count = 0
for a in range(s[0] + 1):
    for b in range(s[1] + 1):
        for c in range(s[2] + 1):
            if( a*500 + b*100 + c*50 == s[3] ):
                count = count + 1

print(ans)


### FIXED CODE ###

s = []
for i in range(4):
    s.append(int(input()))

count = 0
for a in range(s[0] + 1):
    for b in range(s[1] + 1):
        for c in range(s[2] + 1):
            if( a*500 + b*100 + c*50 == s[3] ):
                count = count + 1

print(count)
import math
N=int(input())
A =list(map(int,input().split(' ')))

ans = A[0]
for i in A[1:]:
	ans = math.gcd(ans,i)
print(ans)




### FIXED CODE ###

def gcd(a,b):
	if a == 0:
		return b
	if b == 0:
		return a
	if a < b:
		n = b//a
		return gcd(a,b-n*a)
	else:
		n = a//b
		return gcd(a-n*b,b)

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

ans = A[0]
for i in A[1:]:
	ans = gcd(ans,i)
print(ans)
n,m,*a=map(int,open(0).read().split())
b=[-1]*(n+1)
for i in a:
    b[i]=0
if a[0]==1:
    b[2]=1
elif a[0]==2:
    b[1]=1
else:    
    b[1],b[2]=1,2
for i in range(3,n+1):
    if b[i]!=0:
        b[i]=(b[i-1]+b[i-2])%1000000007
print(b[-1])

### FIXED CODE ###

n,m,*a=map(int,open(0).read().split())
if n==1:
    print(1)
    exit()
b=[-1]*(n+1)
a+=[0,0]
for i in a:
    b[i]=0
if a[0]==1 and a[1]==2:
    b[1],b[2]=0,0
elif a[0]==1:
    b[2]=1
elif a[0]==2:
    b[1]=1
else:    
    b[1],b[2]=1,2
for i in range(3,n+1):
    if b[i]==-1:
        b[i]=(b[i-1]+b[i-2])%1000000007
print(b[-1])
n = int(input())
a = list(map(int, input().split()))
ans =0
for i in range(0,n+1):
    if i%2==0 and a[i]%2!=0:
        ans+=1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
    if i%2==0 and a[i]%2!=0:
        ans+=1
print(ans)
import math
n,k=map(int,input().split())
if n % k == 0:
	x= n//k
	print(x*math.factorial(k))
else:
	r= n % k
	div=n-r
	y=div//k
	sum= y*(math.factorial(k))
	z=nCr(k,r)
	sum+=z
	print(sum)


def nCr(n,r):
    f = math.factorial
    return f(n) / f(r) / f(n-r)

### FIXED CODE ###

n,k=map(int,input().split())
print(k*(k-1)**(n-1))
import sys
import itertools
import numpy as np

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
n = int(readline())
A = list(map(lambda x: x.split(), read().decode().split('\n')))

l = defaultdict(list)
visited = {}
dp = {}

# make topological tree
key = ''
for i in range(n):

    if i + 1 < int(A[i][0]):
        key = '{}-{}'.format(i + 1, A[i][0])
    else:
        key = '{}-{}'.format(A[i][0], i + 1)
    
    visited[key] = False 
    dp[key] = 0 
    prev_key = key

    for j in range(1, n - 1):
        if i + 1 < int(A[i][j]):
            key = '{}-{}'.format(i + 1, A[i][j])
        else:
            key = '{}-{}'.format(A[i][j], i + 1)

        l[prev_key].append(key)
        prev_key = key
        # init visited
        visited[key] = False 
        dp[key] = 0


topo = []
# dp = [0 for i in range(n + 1)]
def dfs(start):
    if visited[start]:
        return dp[start]

    visited[start] = True    
    dp[start] = 0
    for node in l[start]:
        dp[start] = max(dp[start], dfs(node) + 1)

    return dp[start]

ans = 0
for key in list(l):
    ans = max(dfs(key), ans)

print(ans + 1)

# print(l)
# print(topo)
# for node in reversed(topo):


# for noe in topo:

### FIXED CODE ###

import sys
import itertools
import numpy as np

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N = int(readline())
A = [[-1] + [int(x) - 1 for x in row.split()][::-1] for row in readlines()]

# A.append([-1])

def f(cand):
    cand1 = set()
    can_use = []
    for n in cand:
        if A[A[n][-1]][-1] == n:
            can_use.append(n)
    for n in can_use:
        A[n].pop()
        cand1.add(n)
        if A[n][-1] != -1:
            cand1.add(A[n][-1])
    return len(can_use), cand1

answer = 0
rest = N*(N-1)
cand = set(range(N))
while True:
    answer += 1
    x, cand = f(cand)
    if x == 0:
        answer = -1
        break
    rest -= x
    if rest == 0:
        break

print(answer)
#input
N = int(input())
A = np.array(list(map(int, input().split())))

#output
import numpy as np    
idx = np.argsort(-A)

dp = np.zeros((N+1, N+1), int)
#dp[i, j]を左i, 右jまで場所が決まった状態の最大値とする。
#i+j = Nとなる場合の最大値が答えとなる。
for i in range(N):
    dp[i+1, 0] = dp[i, 0] + A[idx[i]]*(abs(idx[i]-i))
for j in range(N):
    dp[0, j+1] = dp[0, j] + A[idx[j]]*(abs(N-1-idx[j]-j))

for i in range(N):
    for j in range(N):
        if i+j+1 < N:
            dp[i+1, j+1] = max(dp[i, j+1]+A[idx[i+j+1]]*(abs(idx[i+j+1]-i)), dp[i+1, j] + A[idx[i+j+1]]*(abs(N-1-idx[i+j+1]-j)))

answer = 0        
for i in range(N):
    answer = max(answer, dp[i, N-i])

print(answer)

### FIXED CODE ###

#python3ではTLE
#input
N = int(input())
A = list(map(int, input().split()))

#output
B = [(i, a) for i, a in enumerate(A)]
B = sorted(B, key = lambda x:x[1], reverse = True)

dp = [[0] * (N+1) for i in range(N+1)]
#dp[i, j]を左i, 右jまで場所が決まった状態の最大値とする。
#i+j = Nとなる場合の最大値が答えとなる。

answer = 0
for i in range(N):
    dp[i+1][0] = dp[i][0] + B[i][1]*(abs(B[i][0]-i))
    for j in range(N):
        dp[0][j+1] = dp[0][j] + B[j][1]*(abs(N-1-B[j][0]-j))
        if i+j+1 < N:
            dp[i+1][j+1] = max(dp[i][j+1]+B[i+j+1][1]*(abs(B[i+j+1][0]-i)), dp[i+1][j] + B[i+j+1][1]*(abs(N-1-B[i+j+1][0]-j)))
    answer = max(answer, dp[i][N-i])

print(answer)
n,x=map(int,input().split())
a=list(map(int,input().split() for i in range(n)))
a_sort=sorted(a)
count=0
sum=0
for i in a_sort:
    while sum+i<=x:
        sum=sum+i
        count+=1
    else:
        break
print(count)


### FIXED CODE ###

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

count=0
if x==sum(a):
    print(n)
elif x>sum(a):
    print(n-1)
else:
    for i in range(n):
        if x>=a[i]:
            count+=1
            x-=a[i]
        else:
            break
    print(count)
N, K = map(int, input().split())
tmp = list(map(int, input().split()))
A = [1]
A.extend(tmp)

# 循環する場所を探す(最大N回)
used = [1, 1]
used.extend([0] * (N-1)) # すでに通った町は1にする
route = [1]
while used[A[route[-1]]] == 0:
    used[A[route[-1]]] = 1
    route.append(A[route[-1]])

if A.index(A[route[-1]]) == 0:
    print(route[K%(len(route))])
else:
    x = A.index(A[route[-1]]) - 1
    y = len(route) - x
    if y == 0:
        print(route[x])
    else:
        print(route[x + (K-x)%y])


### FIXED CODE ###

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

passed = [-1] * (n+1)
route = []
v = 1
while passed[v] == -1:
    passed[v] = len(route)
    route.append(v)
    v = a[v-1]

c = len(route) - passed[v]
l = passed[v]

if k < l:
    print(route[k])
else:
    k -= l
    k %= c
    print(route[l+k])
n=input()
h=n/3600
s=n%3600
m=s/60
s=s%60
print h:m:s

### FIXED CODE ###

S = input()
s = S%60
m = S%3600/60
h = S/3600
print "%d:%d:%d"%(h,m,s)
MOD=10**9+7
N,K=map(int,input().split())
alist=list(map(int,input().split()))
alist.sort()
#print(alist)

inv_table = [0]+[1]
for i in range(2,K+3):
  inv_table.append(-(MOD//i)*inv_table[MOD%i]%MOD)

min_s,max_s=0,0
old_comb,new_comb=0,1
for i in range(K,N+1):
  #print(K,i,new_comb-old_comb)
  min_s+=(new_comb-old_comb)*alist[-1-(i-1)]
  min_s%=MOD
  max_s+=(new_comb-old_comb)*alist[i-1]
  max_s%=MOD
  
  old_comb=new_comb
  new_comb=old_comb*(i+1)*inv_table[i+1-K]%MOD
#print(min_s,max_s)

print((max_s-min_s)%MOD)

### FIXED CODE ###

MOD=10**9+7
N,K=map(int,input().split())
alist=list(map(int,input().split()))
alist.sort()
#print(alist)

inv_table = [0]+[1]
for i in range(2,N+1):
  inv_table.append(-(MOD//i)*inv_table[MOD%i]%MOD)

min_s,max_s=0,0
old_comb,new_comb=0,1
for i in range(K,N+1):
  #print(K,i,new_comb-old_comb)
  min_s+=(new_comb-old_comb)*alist[-1-(i-1)]
  min_s%=MOD
  max_s+=(new_comb-old_comb)*alist[i-1]
  max_s%=MOD
  
  old_comb=new_comb
  new_comb=old_comb*(i+1)*inv_table[i+1-K]%MOD
#print(min_s,max_s)

print((max_s-min_s)%MOD)
num = input()
a = ""
for _ in range(num):
  a += "ACL"
return a

### FIXED CODE ###

num = int(input())
a = ""
for _ in range(num):
  a += "ACL"
print(a)
a,b,c,d=map(int,input().split())
ans1=b//c-(a-1)//c
ans2=b//d-(a-1)//d

import math
e=(c*d)//math.gcd(c,d)
ans3=b//e-(a-1)//e

ans=b-a+1-ans1-ans2+ans3

print(ans)


### FIXED CODE ###

a,b,c,d=map(int,input().split())
ans1=b//c-(a-1)//c
ans2=b//d-(a-1)//d

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y) 
    
e=(c*d)//gcd(c,d)
ans3=b//e-(a-1)//e

ans=b-a+1-ans1-ans2+ans3

print(ans)