Harryxun/stf_run huggingface dataset:
def gcd(n,m):#n,mは正の整数、最大公約数　許容は？
    if n==0:
        return m
    elif m==0:
        return n
    elif n>m:
        n=n%m
        return gcd(n,m)
    else:
        m=m%n
        return gcd(n,m)

def ord(N,n):#N,nは正の整数、Nで割り切れる回数、許容はN^1000
    if n%N!=0:
        return 0
    else:
        return 1+ord(N,n//N)

def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

primelist=get_sieve_of_eratosthenes_new(10**6)

A,B=map(int,input().split())
x=gcd(A,B)
count=1

for i in range(0,len(primelist)):
    if x%primelist[i]==0:
        count+=1
        x=x//primelist[i]**ord(primelist[i],x)
if x!=1:
    count+=1
print(count)

### FIXED CODE ###

N=int(input())
if N%2==0:
    print(0.5)
else:
    print('{:.7g}'.format((N+1)/(2*N)))
INFINITY = float("inf")

N, M, P = [int(e) for e in input().split()]
Es = [None] * M

for i in range(M):
    Es[i] = ([int(e) for e in input().split()])
    Es[i][2] = P - Es[i][2]

d = [INFINITY] * (M + 1)
d[1] = 0

for _ in range(M):
    for e in Es:
        u, v, w = e
        dd = d[u] + w
        if dd < d[v]:
            d[v] = dd

circle_exists = False

for e in Es:
    u, v, w = e

    if v != N:
        continue

    if d[u] + w < d[v]:
        circle_exists = True
        break


if circle_exists:
    print(-1)
else:
    print(max(0, -d[N]))


### FIXED CODE ###

import collections


def bellman_ford(es, n, start):
    infinity = float("inf")
    m = len(es)

    d = [infinity] * (n + 1)
    d[start] = 0

    for _ in range(m):
        updated = False

        for u, v, w in es:
            if d[u] == infinity: continue

            dd = d[u] + w

            if dd < d[v]:
                d[v] = dd
                updated = True

        if not updated: break

    for u, v, w in es:
        if d[u] < infinity and d[u] + w < d[v]:
            return None, True

    return d, False


N, M, P = [int(e) for e in input().split()]

Es = [None] * M

for i in range(M):
    a, b, c = ([int(e) for e in input().split()])
    Es[i] = (a - 1, b - 1, P - c)

q = collections.deque()
q.append(N - 1)

valid = [False] * N
valid[N - 1] = True

while 0 < len(q):
    cur = q.popleft()

    for u, v, _ in Es:
        if cur == v and not valid[u]:
            valid[u] = True
            q.append(u)

es_tmp = []
for e in Es:
    if valid[e[0]] and valid[e[1]]:
        es_tmp.append(e)

Es = es_tmp

distances, le = bellman_ford(Es, N - 1, 0)

if le:
    print(-1)
else:
    print(max(-distances[-1], 0))
n ,m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0
while k > 0:
  i, j = 0
  if a[i] <= b[j]:
    k -= a[i]
    if k >= 0
      i += 1
      ans += 1
      if i >= n:
        for o in range(j, m):
          if k >= b[o]:
            k -= b[o]
            ans += 1
          else:
            k -= b[o]
            break
  else:
    k -= b[j]
    if k >= 0
      j += 1
      ans += 1
      if j >= m:
        for p in range(i, n):
          if k >= a[p]:
            k -= a[p]
            ans += 1
          else:
            k -= a[p]
            break
print(ans)

### FIXED CODE ###

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

a_cs, b_cs = [0], [0]
for i in range(n):
  a_cs.append(a_cs[i] + a[i])
for i in range(m):
  b_cs.append(b_cs[i] + b[i])

ans, j = 0, m
for i in range(n+1):
  if a_cs[i] > k:
    break
  while b_cs[j] > k - a_cs[i]:
    j -= 1
  ans = max(ans, i + j)
print(ans)
S = input()

odd = list(S[::2])
even = list(S[1::2])
xx = "No"
x1 = ""
x2 = ""

for i in range(len(odd)):
  check = 0
  if odd[i] == "L" or "U" or "D":
    check += 1
  
if check == len(odd):
  x1 = "Y"
  
for i in range(len(even)):
  check2 = 0
  if even[i] == "R" or "U" or "D":
    check2 += 1
 
if check2 == len(even):
  x2 = "Y"
  
  
if x1 and x2 == "Y":
  xx = "Yes"
  
  
print(xx)



### FIXED CODE ###

s = input()

if 'L' in s[::2] or 'R' in s[1::2]:
    ans = 'No'
else:
    ans = 'Yes'
print(ans)
s = int(input())
t = input()

if len(t) <= s:
  print(t)
  
else :
  tt =  t[0:s]
  print(tt + "...")

### FIXED CODE ###

a=input()

if int(a)%10 == 3:
	print("bon")
  
elif int(a)%10 == 0:
	print("pon")
    
elif int(a)%10 == 1:
	print("pon")

elif int(a)%10 == 6:
	print("pon")
    
elif int(a)%10 == 8:
	print("pon")    
    
else:
	print("hon")
def main():
    inputs = input().split()
    inputs = [int(i) for i in inputs]

    a = inputs[0]
    b = inputs[1]

    NN = 10 ** 12
    max_n = max([a, b])
    f_list = [True] * max_n

    kouyaku = []

    for n in range(1, int(max_n / 2) + 1):
        if f_list[n]:
            if a % n == 0 and b % n == 0:
                kouyaku.append(n)
            else:
                for i in range(int(max_n / n)):
                    f_list[i] = False

    so = [1]
    for i in kouyaku:
        if i == 1: continue

        f = True
        for j in kouyaku:
            if j == 1 or i < j: continue
            if i != j and i % j == 0:
                f = False
                break
        if f is True:
            so.append(i)

    print(len(so))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import math


def main():
    inputs = input().split()
    inputs = [int(i) for i in inputs]

    a = inputs[0]
    b = inputs[1]

    g = n = gcd(a, b)
    d = {}

    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i:
            continue
        d[i] = i
        while n % i == 0:
            n /= i

    if n != 1:
        d[n] = n

    print(len(d) + 1)


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


if __name__ == "__main__":
    main()
N,K= [int(i) for i in input().split()]
R,S,P= [int(i) for i in input().split()]
n=input()
C=N//K + 1
s=0
for i in range(K):
        m=""
        for j in range(i,N,K):
                if n[j] =='r':
                        if j < K:
                                s+=P
                                m ='r'
                        elif n[j-K]=='r' and m=='r': m =""
                        else:
                                s+=P
                                m ='r'
                elif n[j] =='s':
                        if j < K:
                                s+=R
                                m ='s'
                        elif n[j-K]=='s' and m=='s': m =""
                        else:
                                s+=R
                                m ='s'
                elif n[j] =='p':
                        if j < K:
                                s+=S
                                m ='p'
                        elif n[j-K]=='p' and m=='p': m =""
                        else:
                                s+=S
                                m ='p'               
print(score)


### FIXED CODE ###

N,K= [int(i) for i in input().split()]
R,S,P= [int(i) for i in input().split()]
n=input()
C=N//K + 1
#T = np.zeros((K,C),dtype = int)
#print(T)
score=0

for i in range(K):
        mem=""
        for j in range(i,N,K):
                if n[j] =='r':
                        if j < K:
                                score+=P
                                mem ='r'
                        elif n[j-K]=='r' and mem=='r': mem =""
                        else:
                                score+=P
                                mem ='r'
                elif n[j] =='s':
                        if j < K:
                                score+=R
                                mem ='s'
                        elif n[j-K]=='s' and mem=='s': mem =""
                        else:
                                score+=R
                                mem ='s'
                elif n[j] =='p':
                        if j < K:
                                score+=S
                                mem ='p'
                        elif n[j-K]=='p' and mem=='p': mem =""
                        else:
                                score+=S
                                mem ='p'
                        
print(score)
s = int(input())
count = 0
for i in ragen(len(s)):
    if (i % 2 == 0 and s[i] ==0) or (i % 2 ==1 and s[i] == 1):
        pass
    else:
        count += 1
print(min[count,len(s) - count])

### FIXED CODE ###

s = [int(i) for i in input()]
count = 0
l = len(s)
for i in range(l):
    if (i % 2 == 0 and s[i] ==0) or (i % 2 ==1 and s[i] == 1):
        pass
    else:
        count += 1
print(min([count,l - count]))
a=input()
k=int(input())
x=5*math.pow(10,15)
i=0
while k>0:
    k-=int(str(a)[i])*x
    i+=1
print(str(a)[i-1])

### FIXED CODE ###

a=input()
k=int(input())
if int(a)<10:
    a=str(int(a)*11)
i=0
x=0
while k>=0:
    if a[i]=='1':
        k-=1
        i+=1
        if k==0:
            x=1
            k=-1
    else: 
        k=-1
print(a[i-x])
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N, Q = LI()
    events = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        events.append([s, x])
        events.append([t, -x])
    for _ in range(Q):
        d = II()
        events.append([d, INF])
    events.sort()
    dst = {}
    for t, x in events:
        if x == INF: # query
            y = min(dst) if dst else -1
            print(y)
        elif x > 0: # add
            dst.add(x)
        else: # x < 0, delete
            dst.remove(-x)
    return

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        XST.append([x, s, t])
    D = []
    for _ in range(Q):
        D.append(II())
    ans = [-1] * Q
    nexts = [-1] * Q
    XST.sort()
    for x, s, t in XST:
        i = bisect_left(D, s)
        end = bisect_left(D, t)
        while i < end:
            if nexts[i] == -1:
                ans[i] = x
                nexts[i] = end
                i += 1
            else:
                i = nexts[i]
    for y in ans:
        print(y)
    return

main()
import math

a,b=(int(x) for x in input().split())

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

print(lcm(a, b))

### FIXED CODE ###

import fractions
a, b = map(int, input().split())
print(a * b // fractions.gcd(a, b))
n, k = map(int, input().split())
s = input()
print([s[i].lower() if i == k else s[i] for i in range(n)]

### FIXED CODE ###

n, k = map(int, input().split())
s = input()
print("".join([s[i].lower() if i == k-1 else s[i] for i in range(n)]))
from math import gcd as bltin_gcd


def coprime2(a, b):
    return bltin_gcd(a, b) == 1


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


def cf(x1, x2):
    cf = []
    for i in range(1, min(x1, x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf


c = cf(a, b)
len_c = len(c)

d = [1]
for i in range(1, len(c)):
    coprime_flag = True
    for j in range(0, len(d)):
        if not coprime2(c[i], d[j]):
            coprime_flag = False
            break
    if coprime_flag:
        d.append(c[i])
print(len(d))

### FIXED CODE ###

import math


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


def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct


a, b = map(int, input().split())
c = gcd(a, b)
d = factorize(c)
print(len(set(d))+1)
from sys import stdin

n = int(stdin.readline().rstrip())
data = map(int, stdin.readline().rstrip().split())

def is_s(hens):
  m = max(hens)
  hens.remove(m)
  if m < sum(hens):
  	return True
  else:
    return False

pritn(is_s(data))

### FIXED CODE ###

from sys import stdin
 
n = int(stdin.readline().rstrip())
data = list(map(int, stdin.readline().rstrip().split()))
 
def is_s(hens):
  m = max(hens)
  hens.remove(m)
  if m < sum(hens):
  	return "Yes"
  else:
    return "No"
 
print(is_s(data))
a,b,c = sorted(map(int, input().split()))
if (a+b+c==17)&(a==b)&(c==7):
  return("YES")
else:
  return("NO")

### FIXED CODE ###

a,b,c = sorted(map(int, input().split()))
if (a+b+c==17)&(a==b)&(c==7):
  print("YES")
else:
  print("NO")
n,k = map(int,input().split())
h = list(map(int,input().split()))

dp=[float('inf')]*n
dp[0]=0

for i in range(n):
     for j in range(i+1,min(n,i+k+1)):
          dp[j] = min(dp[j],dp[i] + abs(h[i]-h[j]))
print(dp[-1])
     


### FIXED CODE ###

n = int(input())

h = list(map(int,input().split()))


dp=[float('inf')]*n
dp[0]=0


for i in range(n):
     if  i+1 < n:
          dp[i+1]=min(dp[i+1],dp[i]+abs(h[i]-h[i+1]))
     if  i+2 < n:
          dp[i+2]=min(dp[i+2],dp[i]+abs(h[i]-h[i+2]))
print(dp[-1])
N = int(input())
s = [0] * N
d = {"M": 0, "A": 0, "R": 0, "C": 0, "H": 0}
for i in range(N):
    s[i] = input()
    if s[i][0] == "M":
        d['M'] += 1
    elif s[i][0] == "A":
        d['A'] += 1
    elif s[i][0] == "R":
        d['R'] += 1
    elif s[i][0] == "C":
        d['C'] += 1
    elif s[i][0] == "H":
        d['H'] += 1

total = 1
count = 0
del_keys = []
for k, v in d.items():
    if v == 0:
        del_keys.append(k)
    else:
        total *= v
        count += 1

for key in del_keys:
    del d[key]

if count < 3:
    print(0)
    exit()
elif count == 3:
    print(total)
    exit()
elif count == 4:
    ans = 0
    for k, v in d.items():
        ans += total / v
    print(int(ans))
    exit()
elif count == 5:
    ans = 0
    d_lst = list(d)
    for i in range(4):
        for j in range(i+1, 5):
            ans += total / (d_lst[i] * d_lst[j])
    print(int(ans))


### FIXED CODE ###

from collections import Counter
from itertools import combinations

n = int(input())
s = [input()[0] for _ in range(n)]
lc = Counter(s)

con = []
for c in 'MARCH':
    if c in lc:
        con.append(lc[c])

ans = 0
for a, b, c in combinations(con, 3):
    ans += a * b * c

print(ans)
h,w=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(h)]
ans=[]
for i in range(h):
    for j in range(w-1):
        if a[i][j]%2==1:
            a[i][j+1]+=1
            ans.append([i+1,j+1,i+1,j+2])
for i in range(h-1):
    if a[i][j]==1:
        a[i+1][j]+=1
        ans.append([i+1,j+1,i+2,j+1])
print(len(ans))
for i in ans:
    print(*i)

### FIXED CODE ###

h,w=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(h)]
ans=[]
for i in range(h):
    for j in range(w-1):
        if a[i][j]%2==1:
            a[i][j+1]+=1
            ans.append([i+1,j+1,i+1,j+2])
for i in range(h-1):
    if a[i][w-1]%2==1:
        a[i+1][w-1]+=1
        ans.append([i+1,w,i+2,w])
print(len(ans))
for i in ans:
    print(*i)
def solution(a, b):
    total = a + b
    if (total % 3 == 0) and total >= 3:
        print('Possible')
    else:
        print('Impossible')

A, B = raw_input().split(' ')
A, B = int(A), int(B)

solution((A, B))

### FIXED CODE ###

def solution(a, b):
    total = a + b
    if total % 3 == 0:
        print('Possible')
    elif a % 3 == 0:
        print('Possible')
    elif b % 3 == 0:
        print('Possible')
    else:
        print('Impossible')

A, B = input().split(' ')
A, B = int(A), int(B)

solution(A, B)
N = int(input())
X = input()

xn = X.count('1')
x10 = int(X,2)

def f(one, ten):
    c = 0
    while ten:
        c += 1
        ten %= one
        one = str(bin(ten)).count('1')
    print(c)


for i,j in enumerate(X):
    k = N - 1 - i
    if j == '1':
        f(xn - 1, x10 - (2**k))
    elif j == '0':
        f(xn + 1, x10 + (2**k))


### FIXED CODE ###

l, r, d = map(int, input().split())

ans = 0

for i in range(l, r+1):
    if i % d == 0:
        ans += 1
        
print(ans)
c = 10**18

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

if 0 in a:
    print(0)
    return

for i in a:
    b *= i

if b > c:
    print('-1')
else:
    print(b)

### FIXED CODE ###

def main():
	N = int(input())
	A = list(map(int, input().split()))
	if 0 in A:
		print(0)
		return
	prod = 1
	for a in A:
		prod *= a
		if prod > 1000000000000000000:
			print(-1)
			return
	print(prod)
main()
import sys
import math
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())
def comb(n, k):
    return math.factorial(n) // (math.factorial(n - k) * math.factorial(k))

def era(n):
    lis = [i for i in range(3, n + 1, 2)]
    lis.insert(0, 2)
    for ll in lis:
        lis = [i for i in lis if (i == ll or i % ll != 0)]
    return lis


n = ni()
lis = era(n)
lis2 = [[lis[i], 0] for i in range(len(lis))]
for i in range(1, n + 1):
    for j in lis:
        count = 0
        while(i % j == 0):
            i //= j
            count += 1
        lis2[lis.index(j)][1] += count
c74 = 0
c24 = 0
c14 = 0
c4 = 0
c2 = 0
for i in range(len(lis2)):
    if lis2[i][1] >= 74:
        c74 += 1
    if lis2[i][1] >= 24:
        c24 += 1
    if lis2[i][1] >= 14:
        c14 += 1
    if lis2[i][1] >= 4:
        c4 += 1
    if lis2[i][1] >= 2:
        c2 += 1
ans = 0
ans += comb(c4, 2) * (c2 - 2)
ans += c24 * (c2 - 1)
ans += c14 * (c4 - 1)
ans += c74
print(ans)


### FIXED CODE ###

import sys
import math
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())
def comb(n, k):
    return math.factorial(n) // (math.factorial(n - k) * math.factorial(k))

def era(n):
    lis = [i for i in range(3, n + 1, 2)]
    lis.insert(0, 2)
    for ll in lis:
        lis = [i for i in lis if (i == ll or i % ll != 0)]
    return lis


n = ni()
if n == 1:
    print(0)
    exit()
lis = era(n)
lis2 = [[lis[i], 0] for i in range(len(lis))]
for i in range(1, n + 1):
    for j in lis:
        count = 0
        while(i % j == 0):
            i //= j
            count += 1
        lis2[lis.index(j)][1] += count
c74 = 0
c24 = 0
c14 = 0
c4 = 0
c2 = 0
for i in range(len(lis2)):
    if lis2[i][1] >= 74:
        c74 += 1
    if lis2[i][1] >= 24:
        c24 += 1
    if lis2[i][1] >= 14:
        c14 += 1
    if lis2[i][1] >= 4:
        c4 += 1
    if lis2[i][1] >= 2:
        c2 += 1
ans = 0
ans += comb(c4, 2) * (c2 - 2)
ans += c24 * (c2 - 1)
ans += c14 * (c4 - 1)
ans += c74
print(ans)
import math
from functools import reduce
def b(x, y):
    return (x * y) // math.gcd(x, y)
_ = int(input())
a = [int(x) for x in input().split()]
m = reduce(b, a, 1) - 1
print(sum([m % a_i for a_i in a]))

### FIXED CODE ###

import fractions
from functools import reduce
def b(x, y):
    return (x * y) // fractions.gcd(x, y)
_ = int(input())
a = [int(x) for x in input().split()]
m = reduce(b, a, 1) - 1
print(sum([m % a_i for a_i in a]))
a=[]
n=int(input())
for i in range(10):
        a.append(-1)
while(n!=0):
    b=[]
    c=[]
    a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]=map(int,input().split())
    for i in range(10):
        b.append(-1)
        c.append(-1)
    j=1
    k=0
    lenb=0
    lenc=0
    b[0]=a[0]
    for i in range(1,10):
        if(a[i]>b[j-1]):
            b[j]=a[i]
            j+=1
        else:
            if(k==0):
                c[0]=a[i]
                k+=1
            elif(a[i]>c[k-1]):
                c[k]=a[i]
                k+=1
    for i in range(10):
        if(b[i]!=-1):
            lenb+=1
        if(c[i]!=-1):
            lenc+=1
    if(len(a)==(lenb+lenc)):
        print("YES")
    else:
        print("NO")

### FIXED CODE ###

a=[]
n=int(input())
for i in range(10):
        a.append(-1)
while(n!=0):
    n-=1
    b=[]
    c=[]
    a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]=map(int,input().split())
    for i in range(10):
        b.append(-1)
        c.append(-1)
    j=1
    k=0
    lenb=0
    lenc=0
    b[0]=a[0]
    for i in range(1,10):
        if(a[i]>b[j-1]):
            b[j]=a[i]
            j+=1
        else:
            if(k==0):
                c[0]=a[i]
                k+=1
            elif(a[i]>c[k-1]):
                c[k]=a[i]
                k+=1
    for i in range(10):
        if(b[i]!=-1):
            lenb+=1
        if(c[i]!=-1):
            lenc+=1
    if(len(a)==(lenb+lenc)):
        print("YES")
    else:
        print("NO")
X = int(input())
X = 7 or X = 5 or X =3:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

X = int(input())
if X == 7 or X == 5 or X == 3:
    print("YES")
else:
    print("NO")
, B = (int(i) for i in input().split())
if A%2 == 0:
  a = 0
else:
  a = A
  A = A + 1
if B%2 == 1:
  b = 0
else:
  b = B
  B = B - 1
if (B-A+1)%4==0:
  c = 0
else:
  c = 1
print(a^b^c)

### FIXED CODE ###

A, B = (int(i) for i in input().split())
if A%2 == 0:
  a = 0
else:
  a = A
  A = A + 1
if B%2 == 1:
  b = 0
else:
  b = B
  B = B - 1
if (B-A+1)%4==0:
  c = 0
else:
  c = 1
print(a^b^c)
n=int(input())
A=list(map(int,input().split()))

ans=[]
for i,a in enumerate(A):
  ans.append([i+1,a])
ans.sort(key=lambda x:x[a])
for a in ans:
  print(a[0],end=' ')

### FIXED CODE ###

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

ans=[]
for i,a in enumerate(A):
  ans.append([i+1,a])
ans.sort(key=lambda x:x[1])
for a in ans:
  print(a[0],end=' ')
import numpy as np

N, W = map(int, input().split())
wv = [[0,0]]
for _ in range(N):
    wv.append([ list(map(int, input().split())) ])
# N,W = 3, 8
# wv = [[0,0],[3,30], [4,50], [5,60]]
dp = np.array([ [0]*(W+1) ] * (N+1))
# print(dp.shape)
# print(np.array(dp))

for n in range(1,N+1):
    for w_lim in range(1,W+1):
        # print(n, w_lim)
        # print(np.array(dp))
        # v[n]を追加するとき
        if w_lim - wv[n][0] >= 0 :
            dp[n][w_lim] = max( dp[n-1][w_lim], dp[n-1][w_lim-wv[n][0]]+wv[n][1] )
        else :
            dp[n][w_lim] = dp[n-1][w_lim]

# print('\n',np.array(dp))
print(dp[N][W])


### FIXED CODE ###

import numpy as np

N, W = map(int, input().split())
dp = np.array([ [0]*(W+1) ] * (N+1))
for n in range(1,N+1):
    w, v = map(int, input().split() )
    dp[n][:] = dp[n-1][:]
    dp[n][w:W+1] = np.maximum(dp[n-1][w:W+1], dp[n-1][:W+1-w]+v )
    # for w_lim in range(1,W+1):
    #     if w_lim - wv[n][0] >= 0 :
    #         dp[n][w_lim] = max( dp[n-1][w_lim], dp[n-1][w_lim-wv[n][0]]+wv[n][1] )
    #     else :
    #         dp[n][w_lim] = dp[n-1][w_lim]
print(dp[N][W])