Harryxun/stf_run huggingface dataset:
a,b=map(int,input().split())

List=[]
for i in range(a):
    List.append(input())

print("".join(sorted(List)))

### FIXED CODE ###

a,b,c,=map(int,input().split())
if a+b+c==17:
  print("YES")
else:
  print("NO")
import math
x = int("".join([input(), input()]))

if int(math.sqrt(x))**2 == x:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import math
x = int("".join(input().split()))

if int(math.sqrt(x))**2 == x:
  print("Yes")
else:
  print("No")
##N T
#t1 t2 ... tN
N, T = map(int,input().split())
a = list(map(int, input().split()))
b = []
"""
for i in range(N):
    set1 = set()
    for j in range(T):
        set1.add(a[i] + j)
    b.append(set1)
d = set()
for n in range(len(b)):
    d = d | b[n]
"""
d = set()
for i in range(N):
    d = d | set(range(a[i], a[i] + T))


print(len(d))

### FIXED CODE ###

a, b, c = input().split()
if a[-1] == b[0] and b[-1] == c[0]:
    print("YES")
else:
    print("NO")
N = input()
A=[]
for i in range(N-1):
    A.append(int(input()))
B=sorte(A, reverse=True)
for i in range(N-1):
    if A[i] == B[0]:
        print(B[1])
    else:
        print(B[0]) 

### FIXED CODE ###

N = int(input())
A=[]
for i in range(N):
    A.append(int(input()))
B=sorted(A, reverse=True)
for i in range(N):
    if A[i] == B[0]:
        print(B[1])
    else:
        print(B[0])
N, M, X, Y = map(int, input().split())
x = list(map(int, input().split())).append(X)
y = list(map(int, input().split())).append(Y)
if max(x)<min(y):
	print('War')
else:
	print('No War') 

### FIXED CODE ###

# region header
import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
sys.setrecursionlimit(10**7)
rs = lambda: sys.stdin.readline().rstrip()
ri = lambda: int(rs())
rf = lambda: float(rs())
rs_ = lambda: [_ for _ in rs().split()]
ri_ = lambda: [int(_) for _ in rs().split()]
rf_ = lambda: [float(_) for _ in rs().split()]
INF = float('inf')
MOD = 10 ** 9 + 7
PI = math.pi
# endregion

N, M, X, Y = ri_()
x = ri_()
y = ri_()
ans = 'War'
for Z in range(-100, 101):
    if X < Z <= Y and max(x) < Z and min(y) >= Z:
        ans = 'No War'
print(ans)
n, y = map(int, input().split())

def check(n,y):
    if n == 0 and y == 0:
        return {"truth":True, "a":0, "b":0, "c":0}
    elif n == 0 or y == 0:
        return {"truth":False, "a":-1, "b":-1, "c":-1}
    checkA = check(n-1, y-10000)
    checkB = check(n-1, y-5000)
    checkC = check(n-1, y-1000)
    if  checkA["truth"]:
        checkA["a"] += 1
        return checkA
    elif checkB["truth"]:
        checkB["b"] += 1
        return checkB
    elif checkC["truth"]:
        checkC["c"] += 1
        return checkC
    else:
        return {"truth":False, "a":-1, "b":-1, "c":-1}

print(check(n,y))

### FIXED CODE ###

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

sum = y
wasFound = False
for i in range(n+1):
    if wasFound:
        break
    for j in range(n+1):
        if i+j > n:
            break
        rest = sum - i*10000 - j*5000
        if rest < 0:
            break
        k = int(rest/1000)
        if rest % 1000 == 0 and (i+j+k==n):
            print(i, j, k)
            wasFound = True
            break
if not wasFound:
    print(-1, -1, -1)
from operator import sub

n, k = map(int, input().split())
hhh = sorted(int(input()) for _ in range(n))
print(min(map(sub, zip(hhh[k - 1:], hhh))))


### FIXED CODE ###

n, k = map(int, input().split())
hhh = [int(input()) for _ in range(n)]
hhh.sort()
ans = float('inf')
for i in range(n - k + 1):
    ans = min(ans, hhh[i + k - 1] - hhh[i])
print(ans)
N = int(input())
D, X = map(int, input().split())
A = list()
for _ in range(N):
    A.append(int(input()))

#print(N,D,X,A)
print(sum(A)*D(D+1)/2 + N*D + X)

### FIXED CODE ###

N = int(input())
D, X = map(int, input().split())
A = list()
for _ in range(N):
    A.append(int(input()))


def count_days(a,D):
    count = 1
    for d in range(2,D+1):
        if a*(d-1)+1 <= D:
            count+=1
    return count

print(sum([count_days(a,D) for a in A])+X)
while 1:
    d, w = map(int, input().split())
    if d==w==0:
        break
    E=[list(map(int, input().split())) for i in range(d)]
    a=0
    for x2 in range(d):
        for y2 in range(w):
            for x1 in range(x2-1):
                for y1 in range(y2-1):
                    co=10**18
                    for x in range(x1, x2+1):
                        co=min(co, E[x][y1], E[x][y2])
                    for y in range(y1, y2+1):
                        co=min(co, E[x1][y], E[x2][y])
                    ci=cnt=0
                    for x in range(x1+1, x2):
                        for y in range(y1+1, y2):
                            ci=max(ci, E[x][y])
                            cnt+=E[x][y]
                    if ci < co:
                        a=max(ans, (x2-x1-1)*(y2-y1-1)*co - cnt)
    print(a)



### FIXED CODE ###

while True:
    d, w = map(int, input().split())
    if d == 0:
        break
    area = []
    for _ in range(d):
        area.append(list(map(int, input().split())))
    a = 0
    for dp in range(1, d - 1):
        for wp in range(1, w - 1):
            for i in range(1, d - dp):
                for j in range(1, w - wp):
                    mawari = min(area[i - 1][j - 1:j + wp + 1] + area[i + dp][j - 1:j + wp + 1])
                    naka = 0
                    for ii in range(dp):
                        mawari = min(mawari, area[i + ii][j - 1], area[i + ii][j + wp])
                        naka = max([naka] + area[i + ii][j:j + wp])
                    if mawari > naka:
                        vn = 0
                        for ii in range(dp):
                            for jj in range(wp):
                                vn += mawari - area[i + ii][j + jj]
                        a = max(vn, a)
    print(a)
def rec(s):
  if s == '':
    return True
  else:
    res = False
    res = res or rec(s[7:]) if s[0:7] == 'dreamer' else res
    res = res or rec(s[5:]) if s[0:5] == 'dream' else res
    res = res or rec(s[5:]) if s[0:5] == 'erase' else res
    res = res or rec(s[6:]) if s[0:6] == 'eraser' else res
    return res
  
print('YES' if rec(input()) else 'NO')

### FIXED CODE ###

def solve(s):
  while True:
    if s == '':
      return True
    else:
      if s[0:7] == 'dreamer'[::-1]:
        s = s[7:]
      elif s[0:5] == 'dream'[::-1]:
        s = s[5:]
      elif s[0:5] == 'erase'[::-1]:
        s = s[5:]
      elif s[0:6] == 'eraser'[::-1]:
        s = s[6:]
      else:
        return False
  
print('YES' if solve(input()[::-1]) else 'NO')
# abc111_c_new


from collections import Counter


def solve(n, seq):
    odd = seq[::2]                      # odd numbers of the seq
    even = seq[1::2]                    # even numbers of the seq

    odd = Counter(odd).most_common()    # example -> returns [(1, 5), (2, 5)]
    even = Counter(even).most_common()

    sol = 0
    if odd[0][0] == even[0][0]:
        if len(odd) == 1 and len(even) == 1:
            sol = int(n / 2)
        else:
            if odd[1][1] > even[1][1]:
                sol = n - odd[1][1] - even[0][1]
            else:
                sol = n - odd[0][1] - even[1][1]
    else:
        sol = n - odd[0][1] - even[0][1]

    return sol


if __name__ == "__main__":
    n = int(input())
    seq = list(map(int, input("").split(" ")))
    print(solve(n, seq))


### FIXED CODE ###

# abc_111_a

def transform (bango):
    if bango == "1":
        return "9"
    elif bango == "9":
        return "1"
    else:
        return bango

def solve(string):
    return "".join(list(map(transform, string)))

if __name__ == "__main__":
    string = input("")
    print (solve(string))
# -*- coding: utf-8 -*-

s = input()

double = []
triple = []

for i in range(len(s)-1):
    if s[i] == s[i+1]:
        double = [str(i+1), str(i+2)]
for j in range(len(s)-2):
    if s[i] == s[i+1] == s[i+2]:
        triple = [str(i+1), str(i+3)]
        
if double:
    print(' '.join(double))
elif triple:
    print(' '.join(triple))
else:
    print('-1 -1')
    

### FIXED CODE ###

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

s = input()

ans = ''

for i in range(len(s)-1):
    if s[i] == s[i+1]:
        ans = ' '.join([str(i+1), str(i+2)])
for j in range(len(s)-2):
    if s[j] == s[j+2]:
        ans = ' '.join([str(j+1), str(j+3)])

if ans:
    print(ans)
else:
    print('-1 -1')
n = int(input())
def B(X, n):
    X_dumy = X
    ln = []
    while X_dumy>0:
        ln.append(int(X_dumy%n))
        X_dumy = int(X_dumy/n)
    ln.reverse()
    return ln
ln = B(n, 26)
a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
q = []
print(ln)
for i in range(len(ln)):
    if ln[i] == 1 and ln[i] < ln.index(0):
        q.append('z')
    elif ln[i] != 0:
        q.append(a[ln[i] - 1])
print(''.join(q))

### FIXED CODE ###

N = int(input()) 
ans = '' 
while N > 0:
  N -= 1 
  ans += chr(ord('a') + N % 26)
  N //= 26 
print(ans[::-1])
# Kこの街について，それぞれ横に串刺しにするか縦に串刺しにするかを選んでDFS
N = int(input())

L = [0] * N
for i in range(N):
    X,Y,P = map(int,input().split())
    L[i] = [X,Y,P]

def dfs(XL,YL,PL,K):
    # もう残りのやつがなかったら，０になる
    if not PL:
        return 0
    # 残りがあるけど，全部線を引き終えたら，残りのポイントたちについて距離を計算
    if len(XL)+len(YL)==K+2:
        score = 0
        for x,y,p in PL:
            x_dis = min([abs(x-xl) for xl in XL])
            y_dis = min([abs(y-yl) for yl in YL])
            min_dis = min(x_dis,y_dis)
            score += min_dis*p

        return score
    # それ以外のときは線を引いていく
    score = []
    for i, pl in enumerate(PL):
        x,y,_ = pl
        x = [x]
        y = [y]
        score.append(min(dfs(XL+x,YL,PL[:i]+PL[i+1:],K),dfs(XL,YL+y,PL[:i]+PL[i+1:],K)))
    return min(score)


for i in range(N+1):
    print((dfs([0],[0],L,i)))








### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
# 今の株価が前の日より上がるなら売る，次の日より下がるなら買う．
max_money = 1000
kabu = 0
money = 1000
for i in range(N):
    if i == 0:
        if A[i]<A[i+1]:
            kabu = int(1000/A[i])
            money -= kabu*A[i]
        continue
    if i == N-1:
        if A[i-1]<A[i]:
            money += kabu * A[i]
            kabu = 0
            max_money = max(max_money,money)
        break

    if A[i-1]<A[i]:
        money += kabu * A[i]
        kabu = 0
        max_money = max(max_money,money)
    if A[i]<A[i+1]:
        kabu += int(money/A[i])
        money -= A[i]*int(money/A[i])

print(max_money)
import math


def is_distance_integer(p1, p2):
    n = len(p1)

    total = 0
    for i in range(n):
        total += ((p1[i] - p2[i])**2)

    dist = math.sqrt(total)

    return (dist**2) == total


def count_pairs(points):
    cnt = 0
    n = len(points)

    for i in range(n):
        for j in range(i + 1, n):
            if is_distance_integer(points[i], points[j]):
                cnt += 1

    return cnt


def main():
    N, D = map(int, input().split())

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

    ans = count_pairs(points)

    print(ans)


main()
 


### FIXED CODE ###

import math


def is_distance_integer(p1, p2):
    n = len(p1)

    total = 0
    for i in range(n):
        total += ((p1[i] - p2[i])**2)

    dist = int(math.sqrt(total))

    return (dist**2) == total


def count_pairs(points):
    cnt = 0
    n = len(points)

    for i in range(n):
        for j in range(i + 1, n):
            if is_distance_integer(points[i], points[j]):
                cnt += 1

    return cnt


def main():
    N, D = map(int, input().split())

    points = []
    for _ in range(N):
        points.append(list(map(int, input().split())))

    ans = count_pairs(points)

    print(ans)


main()
a,b = input().split()

print(int(a)*(int(b)*100)/100)


### FIXED CODE ###

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

a = int(a)

b = 100*int(b[0])+10*int(b[2])+1*int(b[3])

print((a*b)//100)
vals = input().split()
dif = vals[0] - vals[1]

if dif >= vals[3]:
  print 0
else:
  print vals[3] - dif

### FIXED CODE ###

vals = [int(x) for x in input(). split()]
dif = vals[0] - vals[1]
 
if dif >= vals[2]:
  print(0)
else:
  print(vals[2] - dif)
A,B,C = map(int,input().split())
print(min(B//A),C)

### FIXED CODE ###

A,B,C = map(int,input().split())
print(min(B//A,C))
n=int(input())
max=0
sum=0
for i in range(n):
  a=int(input())
  if a>=max:
    max=a
  sum=sum+a
if sum-a<a:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

n=int(input())
m=0
s=0
a=list(map(int,input().split()))
for i in range(n):
  if a[i] >= m:
    m=a[i]
  s=s+a[i]
if s-m>m:
  print("Yes")
else:
  print("No")
N, K = map(int, input().split())
A = list(map(int, input().split())) # 消化コスト
F = list(map(int, input().split())) # 食べにくさ
 
import math
import numpy
 
A.sort(reverse = True)
F.sort()

arrA = np.array(A)
arrF = np.array(F)

range_max = max(arrA * arrF) + 1
range_min = max(min((A-K) * B), 0)
 
my_lambda = lambda x: sum([max(math.ceil(A[i] - x/F[i]), 0) for i in range(0, N)]) <= K
 
my_range = range(range_min, range_max)
 
def node(lst):
    len_lst = len(lst)
    if len_lst % 2 == 0:
        mid_idx = int(len_lst/2)
    else:
        mid_idx = int(math.floor(len_lst/2))
 
    if len_lst == 1:
        print(lst[mid_idx])
        return()
 
    if my_lambda(lst[mid_idx-1]) == True:
        left = lst[0:mid_idx]
        node(left)
    else:
        right = lst[mid_idx:]
        node(right)
node(my_range)

### FIXED CODE ###

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

if A < 10 and B < 10:
    print(A*B)
else:
    print(-1)
x,y = map(int, input().split())
 
if (x + y) % 3  == 0:
  print(0)
  exit()
  
k = x - (x+y)//3
m = y - (x+y)//3
 
if k < 0 or m < 0:
  print(0)
  exit()
  
def nCr(k,m):
  mod = 10**9 + 7
  k,m = max(k,m),min(k,m)
  l = s = 0
  for i in range(m,k - m + 1):
    l = l * (m + i) % mod
    s = s * (i + 1) % mod
    
print(l/s)

### FIXED CODE ###

import math
M = 10**9+7
X,Y = map(int,input().split())
if (X+Y)/3 != (X+Y)//3:
    print(0)
    exit()
n = (X+Y)//3
r = Y-n
if r<0 or r>n:
    print(0)
    exit()
 
 
#nCr and Mod
def nCr(n, r, mod=10**9+7):
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod
 
print(nCr(n,r,M))
import math

N, Ma, Mb = map(int,input().split())
rate = Ma / Mb
a = [0] * N
b = [0] * N
c = [0] * N
MA = 0
MB = 0
for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())
    MA += a[i]
    MB += b[i]

dp = [[[math.inf for i in range(MB+1)] for j in range(MA+1)] for k in range(N+1)]
dp[0][0][0] = 0

for it_N in range(N):
    for it_MA in range(MA+1):
        for it_MB in range(MB+1):
            if it_MA >= a[it_N] and it_MB >= b[it_N]:
                if dp[it_N][it_MA-a[it_N]][it_MB-b[it_N]] != math.inf:
                    dp[it_N+1][it_MA][it_MB] = min(dp[it_N][it_MA-a[it_N]][it_MB-b[it_N]] + c[it_N], dp[it_N][it_MA][it_MB])
            else:
                dp[it_N+1][it_MA][it_MB]=dp[it_N][it_MA][it_MB]


ans = -1
for a in range(1, MA+1):
    for b in range(1, MB+1):
        if a/b == rate and dp[N][a][b] != math.inf:
            if ans == -1:
                ans = dp[N][a][b]
            else:
                ans = min(dp[N][a][b], ans)
print(ans)


### FIXED CODE ###


N, Ma, Mb = map(int,input().split())
rate = Ma / Mb
a = [0] * N
b = [0] * N
c = [0] * N
MA = 0
MB = 0
MC = 0
for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())
    MA += a[i]
    MB += b[i]
    MC += c[i]
    
dp = [[[MC for i in range(MB+1)] for j in range(MA+1)] for k in range(N+1)]
dp[0][0][0] = 0

for it_N in range(N):
    for it_MA in range(MA+1):
        for it_MB in range(MB+1):
            if it_MA >= a[it_N] and it_MB >= b[it_N]:
                if dp[it_N][it_MA-a[it_N]][it_MB-b[it_N]] != MC:
                    dp[it_N+1][it_MA][it_MB] = min(dp[it_N][it_MA-a[it_N]][it_MB-b[it_N]] + c[it_N], dp[it_N][it_MA][it_MB])
                else:
                    dp[it_N+1][it_MA][it_MB]=dp[it_N][it_MA][it_MB]
            else:
                dp[it_N+1][it_MA][it_MB]=dp[it_N][it_MA][it_MB]

ans = -1
for a in range(1, MA+1):
    for b in range(1, MB+1):
        if a/b == rate and dp[N][a][b] != MC:
            if ans == -1:
                ans = dp[N][a][b]
            else:
                ans = min(dp[N][a][b], ans)
print(ans)
A = int(input())
B = int(input())
if A < 9 and B < 9:
  print('Yay!')
else:
  print(':(')

### FIXED CODE ###

A, B = map(int, input().split())
if A < 9 and B < 9:
    print('Yay!')
else:
    print(':(')
a,b=map(int,input().split())
p=a+b
m=a-b
j=a*b
i=p
if i<m:
  i=m
if i<j:
  i=j
print i

### FIXED CODE ###

a,b=map(int,input().split())
p=a+b
m=a-b
j=a*b
i=p
if i<m:
  i=m
if i<j:
  i=j
print (i)
H, W, K = map(int, input().split())
C = []
for i in range(H):
    c = str(input())
    C.append(c)
from itertools import combinations
from collections import Counter

def subsets(nums):
    n = len(nums)
    out = []
    for i in range(n+1):
        subout = []
        comb(nums, i, subout)
        out += subout
    return out

def comb(seq, k, out):
    _comb(seq, len(seq), k, 0, [], out)

def _comb(seq, n, k, i, elem, out):
    le = len(elem)
    if le == k:
        out.append(elem)
        return
    for i in range(i, n):
        _comb(seq, n, k, i+1, elem + [seq[i]], out)

def powset(H, W, K, C):
    X = subsets(list(range(W)))
    N = len(X)
    A = []
    for j in range(H):
        a = [0]*N
        for k in range(N):
            for ind in X[k]:
                if C[j][ind] == '#':
                    a[k] += 1
        A.append(a)
    Y = subsets(list(range(H)))
    M = len(Y)
    ans = [0]*(N*M)
    for k in range(N):
        for l in range(M):
            for ind in Y[l]:
                ans[l*M+k] += A[ind][k]
            
    c = Counter(ans)
    return c[K]
        

def Main(H, W, K, C):
    return powset(H, W, K, C)
                    
out = Main(H, W, K, C)
print(out)

### FIXED CODE ###

H, W, K = map(int, input().split())
C = []
for i in range(H):
    c = str(input())
    C.append(c)
from itertools import combinations
from collections import Counter

def subsets(nums):
    n = len(nums)
    out = []
    for i in range(n+1):
        subout = []
        comb(nums, i, subout)
        out += subout
    return out

def comb(seq, k, out):
    _comb(seq, len(seq), k, 0, [], out)

def _comb(seq, n, k, i, elem, out):
    le = len(elem)
    if le == k:
        out.append(elem)
        return
    for i in range(i, n):
        _comb(seq, n, k, i+1, elem + [seq[i]], out)

def powset(H, W, K, C):
    X = subsets(list(range(W)))
    N = len(X)
    A = []
    for j in range(H):
        a = [0]*N
        for k in range(N):
            for ind in X[k]:
                if C[j][ind] == '#':
                    a[k] += 1
        A.append(a)
    Y = subsets(list(range(H)))
    M = len(Y)
    ans = [0]*(N*M)
    for k in range(N):
        for l in range(M):
            for ind in Y[l]:
                ans[l*N+k] += A[ind][k]
            
    c = Counter(ans)
#     print(c)
    if K in c:
        return c[K]
    else:
        return 0
        

def Main(H, W, K, C):
    return powset(H, W, K, C)
                    
out = Main(H, W, K, C)
print(out)
import numpy as np

a = input()
s = list(a)

index = []
index.append(a.find('?')+1)

i = 0
while a.find('?',index[i]) != -1:
  tmp = a.find('?',index[i])
  index.append(tmp + 1)
  i = i + 1

score = a.count('D') + a.count('PD')

for j in range(len(index)):
  if(index[j] != 0):
    if (s[index[j]-2] == 'P'):
      s[index[j]-1] = 'D'
      score = score + 2
    elif (s[index[j]-2] == 'D'):
      if index[j] - 1 < len(a):
        if (a[index[j]] == 'P'):
          s[index[j]-1] = 'D'
          score = score + 1
        elif (a[index[j]] == 'D'):
          s[index[j]-1] = 'P'
          score = score + 1
        elif (a[index[j]] == '?'):
          s[index[j]-1] = 'P'
      else:
        s[index[j]-1] = 'D'
        score = score + 1
s = "".join(s)
print(s)


### FIXED CODE ###

a = input()
s = list(a)

for i in range(len(s)):
  if (a[i] == '?'):
    s[i] = 'D'

s = "".join(s)
print(s)
n = int(input())

l = []
for i in range(2**n,,-1):
  l += ['{:0=3}'.format(int(str(bin(i))[2:]))]

print(l)

### FIXED CODE ###

n = int(input())
la, lxy = [], []
for i in range(n):
  a = int(input())
  la.append(a)
  xy = []
  for j in range(a):
    xy.append(list(map(int, input().split())))
  lxy.append(xy)

lb = []
for i in range(2**n):
  lb += [str(bin(i))[2:].zfill(n)]
lc = [sum(int(j) for j in i) for i in lb]
lc, lb = zip(*sorted(zip(lc, lb), reverse=True))
lb = [[int(j) for j in i] for i in lb]

for l in lb:
  ok = 1
  for i in range(n):
    a = la[i]
    for j in range(a):
      x, y = lxy[i][j]
      if l[i] == 1 and l[x-1] != y:
        ok = 0
        break
  if ok:
    print(sum(int(k) for k in l))
    break
else:
  print(0)
import numpy as np
n, W = map(int, input().split())
dp = np.zeros((n + 1, W + 1))

for i in range(n):
    w, v = map(int, input().split())
    dp[i + 1] = dp[i]
    if w <= W:
        dp[i + 1][w:] = np.maximum(dp[i][:W - w + 1] + v, dp[i][w:])
print(int(dp[n][W]))

### FIXED CODE ###

n, W = map(int, input().split())
dp = [W + 1] * (1010 * (n + 1))

dp[0] = 0
v_max = 0
for i in range(n):
    w, v = map(int, input().split())
    v_max += v
    for j in range(v_max, v - 1, -1):
        dp[j] = min(dp[j - v] + w, dp[j])

ans = 0
for i in range(v_max, -1, -1):
    if dp[i] <= W:
        ans = max(ans, i)
print(ans)
x, k, d = map(int, input().split())
x = abs(x)

if d*k < x:
    print(abs(x)-abs(d*k))
else:
    if abs(x%d-d) > abs(x%d):
        if (k-x//d)%2 == 0:
            print(abs(x%d))
        else:
            print(abs(x%d-d))
    elif abs(x%d-d) < abs(x%d)
        if (k-x//(d+1))%2 == 0:
            print(abs(x%d-d))
        else:
            print(abs(x%d))


### FIXED CODE ###

x, k, d = map(int, input().split())
x = abs(x)

if d*k < x:
    print(x-d*k)
else:
    if (k-x//d)%2 == 0:
        print(x%d)
    else:
        print(abs(x%d-d))
N = int(input())
A = list(map(int, input().split()))

A = sorted(A, reverse=True)

ans = 0
for i in range(N-1):
    B = A[(i+1):]
    if all(A[i] % B[j] != 0 for j in range(len(B))):
        ans += 1

if A[-1] != A[-2]:
    ans += 1

print(ans)

### FIXED CODE ###

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

A.sort()
A_max = A[-1]

checked = [False] * (A_max+1)
ans = 0
for i in range(N):
    if i < N-1:
        if A[i] == A[i+1]:
            for j in range(A[i], A_max+1, A[i]):
                checked[j] = True
    if checked[A[i]]:
        pass
    else:
        ans += 1
        for j in range(A[i], A_max+1, A[i]):
            checked[j] = True

print(ans)