Harryxun/stf_run huggingface dataset:
N, W = map(int, input().split(" "))
items = [tuple(map(int, input().split(" "))) for _ in range(N)]
dp = [[0]*(W+1) for i in range(N+1)]

for i in range(1, N+1):
    w, v = items[i-1]
    for j in range(1, W+1):
        if j >= w:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][W])

### FIXED CODE ###

N = int(input().strip())
h = [[0] * (N+1) for i in range(3)]
for i in range(1, N+1):
    a, b, c = map(int, input().split(" "))
    h[0][i] = max(h[1][i-1], h[2][i-1]) + a
    h[1][i] = max(h[0][i-1], h[2][i-1]) + b
    h[2][i] = max(h[0][i-1], h[1][i-1]) + c

print(max(h[0][N], h[1][N], h[2][N]))
a, b = map(int,input().split())

def lcm(a,b):
  return a*b//gcd(a,b)
 print(lcm(a,b))

### FIXED CODE ###

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

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

def lcm(a,b):
  return a*b//gcd(a,b)
print(lcm(a,b))
n, m = map(int, input().split())
sc = [list(map(int, input().split())) for i in range(m)]
ans =[0]*n
flag = False
for i in range(m):
    for j in range(m):
        if sc[i][0] == sc[j][0] and sc[i][1] != sc[j][1]:
            flag = True
            

for i in range(m):
    ans[sc[i][0]-1] = sc[i][1]

if flag or ans[0] == 0:
    print(-1)
else:
    print(ans[0]*100 + ans[1]*10 + ans[2])

### FIXED CODE ###

n, m = map(int, input().split())
sc = [tuple(map(int, input().split())) for _ in range(m)]

flag = True

if n == 1 and m == 0:
    print(0)
elif n == 1 and m != 0:
    if len(set(sc)) != 1:
        print(-1)
    else:
        print(sc[0][1])
        
        
elif n > 1 and m == 0:
    print(10**(n-1))
    
elif n > 1 and m != 0:
    for i in range(10**(n-1), 10**n):
        i_str = str(i)
        i_list = list(i_str)
        for item in set(sc):
            if i_list[item[0]-1] != str(item[1]):
                break
        else:
            print(i)
            flag = False
            break
    if flag:
        print(-1)
import itertools

N,M=map(int,input().split())
a=[int(input()) for _ in range(M)]

def count_step(n):
    num=n//2
    count=0
    for i in range(num+1):
        step=[]
        for _ in range(n-2*i):
            step.append(1)
        for _ in range(i):
            step.append(2)
        count+=len(list(itertools.combinations(step,i)))
    return count

a2=[a[0]-1]

for i in range(M-1):
    p=a[i+1]-a[i]-2
    
    a2.append(p)

a2.append(N-a[M-1]-1)

p=1
for i in range(M-1):
    if a[i]+1==a[i+1]:
        p=0
        break

if p==0:
    pattern=0
else:
    pattern=1
    for i in range(len(a2)):
        pattern*=count_step(a2[i])

print(pattern%1000000007)

### FIXED CODE ###

N,M=map(int,input().split())
a=[0]
for _ in range(M):
    a.append(int(input()))

b=[]
num=0
if len(a)>1:
    b.append(a[1]-a[0]-1)
    for i in range(1,M):
            b.append(a[i+1]-a[i]-2)
    b.append(N-a[M]-1)
else:
    b.append(N)

num=max(b)


mod=1000000007

def fib(n,num):
    fib=[0 for i in range(num+10)]
    fib[0]=1
    fib[1]=1
    for i in range(2,num+1):
        fib[i]=fib[i-1]+fib[i-2]
    return fib[n]

if -1 in b:
    print(0)
else:
    p=1
    for j in range(M+1):
        p*=fib(b[j],num)
    print(p%mod)
n, p = map(int, input().split())
if n == 1:
    print(p)
else:
    ans = 1
    for i in range(2, int(p ** (1 / n)) + 1):
        if p % (i ** n) == 0:
            ans = i
    if ans == 1:
        if p % ((i + 1) ** n) == 0:
            ans = i + 1
    print(ans)

### FIXED CODE ###

import collections

def prime_return(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n, p = map(int, input().split())
t = collections.Counter(prime_return(p))
ans = 1
for k, v in t.items():
    if v >= n:
        ans *= (k ** (v // n))
print(ans)
import numpy as np
h, w = map(int, input().rstrip("\n").split())

array = np.array([[" "] * (w + 2)] + [list(" " + input().rstrip("\n") + " ") for _ in range(h)] + [[" "] * (w + 2)])

list_ = []

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if array[i][j] == "#":
            list_.append("#")
        else:
            list_.append(str(sum(sum(array[i - 1:i + 2, j - 1:j + 2] == "#"))))
    list_.append("\n")
list_.pop()

print("".join(list_))


### FIXED CODE ###


import numpy as np
h, w = map(int, input().rstrip("\n").split())

array = np.array([[" "] * (w + 2)] + [list(" " + input().rstrip("\n") + " ") for _ in range(h)] + [[" "] * (w + 2)])

list_ = []

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if array[i][j] == "#":
            list_.append("#")
        else:
            list_.append(str(sum(sum(array[i - 1:i + 2, j - 1:j + 2] == "#"))))
    list_.append("\n")
list_.pop()

print("".join(list_))
n = input()
a = list(map(int, input().split()))
max_a_list = [0]*n
max_a_list[0] = a[0]

for i in range(1,n):
  max_a_list[i] = max(max_a_list[i - 1],a[i])
sum_ = 0
for i in range(n):
  if max_a_list[i] > a[i]:
    sum_ += max_a_list[i] - a[i]
print(sum_)



### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
max_a_list = [0]*n
max_a_list[0] = a[0]

for i in range(1,n):
  max_a_list[i] = max(max_a_list[i - 1],a[i])
sum_ = 0
for i in range(n):
  if max_a_list[i] > a[i]:
    sum_ += max_a_list[i] - a[i]
print(sum_)
INF = float('inf')
dp = [INF] * (10**5 + 10)
dp[0] = 0
h = [0] * (10 ** 4)
N, K = map(int, input().split())
h = list(map(int, input().split())) + h
for i in range(N):
    for k in range(1, K+1):
        dp[i+k] = min(dp[i+k], dp[i] + abs(h[i] - h[i+k]))
print(dp[N-1])


### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
INF = float('inf')
dp = [INF] * (1 + 10 ** 5)
dp[0] = 0
for i in range(n):
    for j in range(1, k + 1):
        if i - j < 0:
            continue
        dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))
print(dp[n-1])
from math import ceil
h,w =map(int,input(),split())
ss = (ceil(h/2)*ceil(w/2))+(h//2*w//2)
if h>1 and w>1:
	print(ss)
else:
  print(1)

### FIXED CODE ###

a,b =map(int,input().split())
ss = a*b
hf =ss//2
if a>1 and b>1:
	print(ss-hf)
else:
  print(1)
l = len(input())
out = "x"*l
peint(out)

### FIXED CODE ###

l = len(input())
out = "x"*l
print(out)
x, n = map(int, input().split())
if n != 0:
    p = list(map(int, input().split()))
    if x in p:
        for i in range(-1000, 1001):
            print(i)
            if i == -100:
                mini = i
            if i in p:
                pass
            else:
                if abs(x - mini) > abs(x - i):
                    mini = i
                elif abs(x - mini) == abs(x - i):
                    mini = min(mini, i)
        else:
            print(mini)
    else:
        print(x)
else:
    print(x)


### FIXED CODE ###

x, n = map(int, input().split())
if n != 0:
    p = list(map(int, input().split()))
    if x in p:
        for i in range(-1000, 1001):
            if i == -1000:
                mini = i
            if i in p:
                pass
            else:
                if abs(x - mini) > abs(x - i):
                    mini = i
                elif abs(x - mini) == abs(x - i):
                    mini = min(mini, i)
        else:
            print(mini)
    else:
        print(x)
else:
    print(x)
import bisect


def mizuyari(flowers):
    if flowers == []:
        return 0
    # print(flowers)
    minheight = min(flowers)
    if minheight == 0:
        if max(flowers) == 0:
            return 0
        leftindex = flowers.index(0)
        # print("分割"+str(leftindex)+" "+str(rightindex))
        count = mizuyari(flowers[0:leftindex])+mizuyari(flowers[leftindex:])
        return count
    else:
        count = mizuyari([i - minheight for i in flowers]) + minheight
        return count


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

print(mizuyari(h_list))


### FIXED CODE ###

import bisect


def mizuyari(flowers):
    if flowers == []:
        return 0
    # print(flowers)
    minheight = min(flowers)
    if minheight == 0:
        if max(flowers) == 0:
            return 0
        leftindex = flowers.index(0)
        # print("分割" + str(leftindex))
        if leftindex == len(flowers):
            count = mizuyari(flowers[0:leftindex])
        else:
            count = mizuyari(flowers[0:leftindex]) + \
                mizuyari(flowers[leftindex+1:])

        return count
    else:
        count = mizuyari([i - minheight for i in flowers]) + minheight
        return count


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

print(mizuyari(h_list))
N,T = map(int,input().split())
t = 1001
for i in range(N) :
    c,t = map( int, input().split() )
    if t<=T:
        m = min(m,c)
    print('TLF' if m==1001 else m)

### FIXED CODE ###

N,T = map(int,input().split())
m = 1001
for i in range(N) :
    c,t = map( int, input().split() )
    if t<=T:
        m = min(m,c)
print('TLE' if m==1001 else m)
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define rrep(i,n) for(int i=1; i<=(int)(n); i++)
#define pb push_back
#define all(v) v.begin(),v.end()
#define fi first
#define se second
#define bigger (char)toupper
#define smaller (char)tolower
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<string> vs;
typedef vector<char> vc;
typedef long long ll;
typedef unsigned long long ull;

int main() {
    ll A,B,C;
    cin>>A>>B>>C;
    if(A%2==0||B%2==0||C%2==0) cout<<0<<endl;
    else {
        vector<ll> v;
        v.pb(A);
        v.pb(B);
        v.pb(C);
        sort(all(v));
        cout<<v[0]*v[1]<<endl;
    }
}

### FIXED CODE ###

A,B,C = map(int,input().split())
if A%2==0 or B%2==0 or C%2==0:
  print(0)
else:
  print(A*B*C//max({A,B,C}))
N = int(input().strip())
arrayH = list(map(int, input().strip().split(' ')))
ans = 1
i = 0
while arrayH[i] <= arrayH[i+1]:
                ans = i + 1
                i = i + i
                if i == N - 1:
                        break
print(ans)


### FIXED CODE ###

N = int(input().strip())
arrayH = list(map(int, input().strip().split(' ')))
ans = 1
for i in range(N - 1):
        yn = True
        for j in range(i+1):
                if arrayH[j] > arrayH[i+1]:
                        yn = False
        if yn:
                ans = ans + 1
print(ans)
n=int(input())
h=list(map(int,input().split()))
x=[]
c=0
for i in range(n-1):
    if h[i]>=h[i+1]:
        c+=1
        x.append(c)
    else:
        c=0
        x.append(c)
print(max(x))

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
x=[]
c=0
if n==1:print(0)
else:
    for i in range(n-1):
        if h[i]>=h[i+1]:
            c+=1
            x.append(c)
        else:
            c=0
            x.append(c)
    print(max(x))
n = int(input())
t,a = map(int(input().split()))
h = list(map(int,input().split()))
deg = 11451419
for i in range(n):
  if deg > abs(a - h[i]*0.006):
    deg = abs(a - h[i]*0.006)
    ans = i+1
print(ans)

### FIXED CODE ###

n = int(input())
t,a = map(int,input().split())
h = list(map(int,input().split()))
deg = 11451419
for i in range(n):
  if deg > abs(a - (t - h[i]*0.006)):
    deg = abs(a - (t - h[i]*0.006))
    ans = i+1
print(ans)
from itertools import permutations

n,m=map(int,input().split())
path=set()
for _ in range(m):
    u,v=map(int,input().split())
    path|={(u-1,v-1),(v-1,u-1)}
s = 0
for i in permutations(range(n)):
    s+=(all((h,j) in path for h,j in zip(i[1:],i))) if i[0] ==0
print(s)

### FIXED CODE ###

#########
#thiking Face
from itertools import permutations

n,m=map(int,input().split())
path=set()
for _ in range(m):
    u,v=map(int,input().split())
    path|={(u-1,v-1),(v-1,u-1)}

print(sum(all((u,v) in path for u,v in zip(p,p[1:]))
          for p in permutations(range(n)) if p[0]==0))
H, W=map(int, input().split())
m=[[-1 for i in range(W+2)]]
mm=[[-1]+[0 for j in range(W)]+[-1] for i in range(H)]
m=m+mm+m
m[1][1]=1

counter0=0
for i in range(1, H+1):
  c=input()
  for j in range(1, W+1):
    if c[j-1]=='#':
      mm[i][j]=-1
    else:
      counter0+=1
      
def f(math, kazu, h, w):
  cha=0
  for i in range(1, h+1):
    for j in range(1, w+1):
      if math[i][j]==kazu:
        if math[i-1][j]==0:
          math[i-1][j]=kazu+1
          cha=1
        if math[i+1][j]==0:
          math[i+1][j]=kazu+1
          cha=1
        if math[i][j-1]==0:
          math[i][j-1]=kazu+1
          cha=1
        if math[i][j+1]==0:
          math[i][j+1]=kazu+1
          cha=1
  return math, cha

cha=1
i=1
while cha==1:
  m, cha=f(m, i, H, W)
  i+=1
  
if m[H][W]==0:
  out=-1
else:
  out=counter0-m[H][W]
  
print(out)

### FIXED CODE ###

H, W=map(int, input().split())
m=[[-1 for i in range(W+2)]]
mm=[[-1]+[0 for j in range(W)]+[-1] for i in range(H)]
m=m+mm+m
m[1][1]=1

counter0=0
for i in range(1, H+1):
  c=input()
  for j in range(1, W+1):
    if c[j-1]=='#':
      m[i][j]=-1
    else:
      counter0+=1
      
def f(math, kazu, h, w):
  cha=0
  for i in range(1, h+1):
    for j in range(1, w+1):
      if math[i][j]==kazu:
        if math[i-1][j]==0:
          math[i-1][j]=kazu+1
          cha=1
        if math[i+1][j]==0:
          math[i+1][j]=kazu+1
          cha=1
        if math[i][j-1]==0:
          math[i][j-1]=kazu+1
          cha=1
        if math[i][j+1]==0:
          math[i][j+1]=kazu+1
          cha=1
  return math, cha

cha=1
i=1
while cha==1:
  m, cha=f(m, i, H, W)
  i+=1
  
if m[H][W]==0:
  out=-1
else:
  out=counter0-m[H][W]
  
print(out)
L=[]
i=0
while i <10000:
    L.append(0)
    i+=1
for x0 in range(1,100):
    for y0 in range(1,100):
        for z0 in range(1,100):
            p=x0**2+y0**2+z0**2+x0*y0+y0*z0+z0*x0
            if p<10000:
                L[p]+=1
N=int(input())
for i in range(1,N+1):
    print(L[i])

### FIXED CODE ###

L=[]
i=0
while i <100001:
    L.append(0)
    i+=1
for x0 in range(1,100):
    for y0 in range(1,100):
        for z0 in range(1,100):
            p=x0**2+y0**2+z0**2+x0*y0+y0*z0+z0*x0
            if p<10001:
                L[p]+=1
N=int(input())
for i in range(1,N+1):
    print(L[i])
x,a,b = (int(x) for x in input().split())
if a < b:
  if b-a > c:
    print ('dengerous')
  else:
    print ('safe')
else:
  print ('delicious')


### FIXED CODE ###

x,a,b = (int(i) for i in input().split())
if a < b:
  if b-a > x:
    print ('dangerous')
  else:
    print ('safe')
else:
  print ('delicious')
array = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k = int(input())
print(array[k+1])


### FIXED CODE ###

array = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k = int(input())
print(array[k-1])
from numpy import zeros
n, m = map(int, input().split())
h = list(map(int,input().split()))
t = zeros((n, n), dtype=int)
for j in range(m):
    a, b = map(int, input().split())
    t[a-1][b-1] = 1
    t[b-1][a-1] = 1
ans = [1]*n
for i in range(n):
    for j in range(n):
        if t[i][j] == 1:
            if h[i] <= h[j]:
                ans[i] *= 0
                break
print(sum(ans))

### FIXED CODE ###

n, m = map(int, input().split())
h = list(map(int,input().split()))
ans = [1]*n
for j in range(m):
    a, b = map(int, input().split())
    if h[a-1] <= h[b-1]:
        ans[a-1] *= 0
    if h[b-1] <= h[a-1]:
        ans[b-1] *= 0
print(sum(ans))
X='abcdefghijklmnopqrstuvwxyz'*2
S=input()
k=int(input())
N=[]
for s in S:
    if s=='a':
        N.append(0)
    else:
        N.append(26-X.index(s))
ans=''
for i in range(len(S)):
    if N[i]<=k :
        k-=N[i]
        ans+='a'
    else:
        ans+=S[i]
ans=ans[:-1]+X[X.index(ans[i])+k]

print(ans)

### FIXED CODE ###

X='abcdefghijklmnopqrstuvwxyz'*2
S=input()
k=int(input())
N=[]
for s in S:
    if s=='a':
        N.append(0)
    else:
        N.append(26-X.index(s))
ans=''
for i in range(len(S)):
    if N[i]<=k :
        k-=N[i]
        ans+='a'
    else:
        ans+=S[i]
ans=ans[:-1]+X[X.index(ans[-1])+k%26]

print(ans)
n=int(input())

m=-1

for i in range(3,1000,2):
    if i*i==8*n+1:
        m=(1+i)//2

if m==-1:
    print('No')
    exit(0)

cnt=1
s=[[0] for _ in range(n+1)]

for i in range(1,m+1):
    for j in range(i+1,m+1):
        s[i][0]+=1
        s[j][0]+=1

        s[i].append(cnt)
        s[j].append(cnt)

        cnt+=1

print('Yes')
print(m)
for i in range(1,m+1):
    print(' '.join([str(c) for c in s[i]]))

### FIXED CODE ###

n=int(input())

m=-1

for i in range(3,1000,2):
    if i*i==8*n+1:
        m=(1+i)//2

if m==-1:
    print('No')
    exit(0)

cnt=1
s=[[0] for _ in range(m+1)]

for i in range(1,m+1):
    for j in range(i+1,m+1):
        s[i][0]+=1
        s[j][0]+=1

        s[i].append(cnt)
        s[j].append(cnt)

        cnt+=1

print('Yes')
print(m)
for i in range(1,m+1):
    print(' '.join([str(c) for c in s[i]]))
a, b, c, d = map(int, input())
print('Yes' if abs(a-c) <= d or max(abs(a-b), abs(b-c)) <= d else 'No')

### FIXED CODE ###

a, b, c, d = map(int, input().split())
print('Yes' if abs(a-c) <= d or max(abs(a-b), abs(b-c)) <= d else 'No')
N, K = map(int, input().aplit())
print(N - K + 1)

### FIXED CODE ###

N, K = map(int, input().split())
print(N-K+1)
a,b,x=map(int,input().split())
n=b-a+1
l=[0]*(n+1)
init=a
for i in range(1,n+1):
    if init%x==0:
        l[i]=l[i-1]+1
    else:
        l[i]=l[i-1]
    init+=1

print(l[-1]-l[0])

### FIXED CODE ###

#48-B
a,b,x=map(int,input().split())
b_count=b//x
a_count=(a-1)//x
print(b_count-a_count)
r,g,b = input().split()
if int(r+g+b)%4==0: print('YES')
else print('NO')

### FIXED CODE ###

r,g,b = input().split()
if int(r+g+b)%4==0: print('YES')
else: print('NO')
friends=input()
friends.split('')
friends_all=friends[0]
friends_cakes=friends[1]
person=int(friends_all)+1
cakes=input()
cakes_amount=0
for a in cakes.split(''):
        cakes_amount+=int(a)
one_person=cakes_amount//person

if cakes_amount%person!=0:
        one_person+=1
else:
        pass
print(one_person)



### FIXED CODE ###

friends=input()
friends=friends.split()
friends_all=friends[0]
person=int(friends_all)+1
cakes=input()
cakes_amount=0
for a in cakes.split():
        cakes_amount+=int(a)
one_person=cakes_amount//person

if cakes_amount%person!=0:
        one_person+=1
else:
        pass
print(one_person)
x,a,b=map(int,input().split())
if (b-a)%2 == 0:
    print((b-a)//2)
else:
    print(min( a + (b-a-1)//2, n - b + 1 + (b-a-1)//2) )
    

### FIXED CODE ###

x,a,b=map(int,input().split())
if (b-a)%2 == 0:
    print((b-a)//2)
else:
    print(min( a + (b-a-1)//2, x - b + 1 + (b-a-1)//2) )
N, X = list(map(int, input().split())) # 整数
list_temp = []
list_temp.append(list(map(int, input().split())))

list = list_temp[0]
list_dev = []

#公約数の関数作成
def devisor(x):
    list_div = []
    for i in range(1,x+1):
        if x % i == 0:
            list_div.append(i)
    return list_div

#xiとXの絶対値をとって、各絶対値の最大公約数を算出
for i in list:
    abs_temp = abs(i - X)
    list_dev += devisor(abs_temp)

l_dupli = [i for i in set(list_dev) if list_dev.count(i) > 2]
print(l_dupli[-1])

### FIXED CODE ###

import functools as ft
 
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)
 
def gcd_list(numbers):
    return ft.reduce(gcd,numbers)
 
N, X = map(int, input().split(" "))
Xi = [int(a) for a in input().split()]
 
def MinusX(Xi_):
    return abs(Xi_-X)
 
def main(Xi):
    Xi = map(MinusX,Xi)
    output = gcd_list(Xi)
    print(output)
 
if __name__ == "__main__":
    main(Xi)
if n & 1 == 0:
        print((n // 2) ** 2)
    else:
        print((n // 2) * (n // 2 + 1))

### FIXED CODE ###

n = int(input())
if n&1==0:
    print((n//2)**2)
else:
    print((n//2)*(n//2+1))
use std::io::stdin;
use std::collections::BTreeMap;

fn main() {
    let mut buf = String::new();
    stdin().read_line(&mut buf).ok();
    let n: usize = buf.trim().parse().ok().unwrap();

    let mut buf = String::new();
    stdin().read_line(&mut buf).ok();
    let a =  buf.split_whitespace().map(|x| x.parse().ok().unwrap()).collect::<Vec<usize>>();

    let mut like = BTreeMap::new();

    let mut ans = 0usize;

    for (i, t) in a.iter().enumerate() {
        let handle = like.entry(i+1).or_insert(0);
        *handle = *t;
        if like.get(t) == Some(&(i+1)) {
            ans += 1;
        }
    }

    println!("{}", ans);
}



### FIXED CODE ###

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

like = {}
ans = 0

for i, r in enumerate(a):
    like[i+1] = r
    if r in like and like[r] == i+1:
        ans += 1

print(ans)
x = int(input())
ans = set()
for b in range(1,x):
    for p in range(2,x):
        if pow(b,p) > x:
            break
        else:
            ans.add(pow(b,p))
    if max(ans) > x:
        break
print(max(ans))


### FIXED CODE ###

x = int(input())
ans = 1
for b in range(1,x):
    for p in range(2,x):
        a = b**p
        if a == a // 1 and a > ans and a <= x:
            ans = a
        if a>x:
            break
    if a > x:
        continue
print(ans)
import collections

N=int(input())

a_dict=collections.Counter(a)
a=list(a_dict.items())

L=len(a)

ans=0
for i,n in a_dict.items():
    if i>n:
        ans+=n
    elif i<n:
        ans+=n-i

print(ans)

### FIXED CODE ###

import collections

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

a_dict=collections.Counter(a)

ans=0
for i,n in a_dict.items():
    if i>n:
        ans+=n
    elif i<n:
        ans+=n-i

print(ans)
n, l = map(int, input().split())
t = list(map(lambda x: l + x, range(n)))
r = sum(t)
for i in range(n):
    tmp = sum(t[:i] + t[i + 1:])
    dif_t = abs(r - tmp)
    if i == 0:
        dif = dif_t
    if dif_t < dif:
        ans = tmp
        dif = dif_t
print(ans)


### FIXED CODE ###

n, l = map(int, input().split())
t = list(map(lambda x: l + x, range(n)))
r = sum(t)
dif = 10 ** 100
for i in range(n):
    tmp = sum(t[:i] + t[i + 1:])
    dif_t = abs(r - tmp)
    if dif_t < dif:
        ans = tmp
        dif = dif_t
print(ans)
def main():
    n, m = map(int, input().split())
    query = []
    result =  [[] for i in range(n)]
    for i in range(m):
        qList = list(map(int, input().split()))
        query.append(qList)
        result[qList[0]-1].append(qList[1])
 
    for i in result:
        i.sort()
 
    for city in query:
        rank = bisect.bisect_left(result[city[0]-1], city[1])
        ans = "%06d%06d"%(city[0],rank+1)
        print(ans)
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    from sys import stdin
    from bisect import bisect_left

    readline = stdin.readline
    n, m = map(int, readline().split())
    data = [list(map(int, readline().split())) for _ in range(m)]
    t = [[] for _ in range(n)]

    for p, y in data:
        t[p - 1].append(y)

    for i in range(n):
        t[i].sort()

    for p, y in data:
        nth = bisect_left(t[p - 1], y) + 1
        print("%06d%06d" % (p, nth))

main()
n,k = map(int, input().split())
h = [int(input()) for i in range(n)] 
h.sort()

crr_min = 10^9

for i in range(0,n-k+1):
    tmp = h[n-k+i] - h[0+i]
    if tmp<crr_min:
        crr_min=tmp

print(crr_min)




### FIXED CODE ###

import math

n,k = map(int, input().split())
h = [int(input()) for i in range(n)] 
h.sort()

crr_min = 10**9

for i in range(0,math.ceil((n-k+1)/2)):
    tmp1 = h[i+k-1] - h[i]
    tmp2 = h[-1-i] - h[-i-k]
    if tmp1==0 or tmp2==0:
        crr_min=0
        break

    if tmp1<crr_min:
        crr_min = tmp1

    if tmp2<crr_min:
        crr_min = tmp2


print(crr_min)
import math

N = int(input())
X = int(input())
m = {}
num = 0


for i in range(N):
  m[i] = int(input())
  X = X - m[i]
  num += 1

print(math.floor(X / min(m[i] for i in m) + num))


### FIXED CODE ###

import math

N, X = map(int, input().split())
m = {}
num = 0


for i in range(N):
  m[i] = int(input())
  X = X - m[i]
  num += 1

print(math.floor(X / min(m[i] for i in m) + num))
n,k=map(int,input().split())
h=list(map(int,input().split()))
cost=[float("inf")]*n
cost[0]=0
for i in range(n-1):
    for j in range(1,min(k+1,n-i):
        cost[i+j]=min(cost[i+j],cost[i]+abs(h[i+j]-h[i]))

print(cost[-1])


### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
cost=[float("inf")]*n
cost[0]=0
for i in range(n-1):
    for j in range(1,min(k+1,n-i)):
        cost[i+j]=min(cost[i+j],cost[i]+abs(h[i+j]-h[i]))

print(cost[-1])