Harryxun/stf_run huggingface dataset:
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def prime_factorize(n):
    '''
    素因数分解のリストを返す。n == 1のとき[]になるので注意。
    :param n:int
    素因数分解する自然数
    :return: list
    素因数分解した結果。

    例
    n : 10
    primes : [[2, 1], [5, 1]]
    '''
    primes = []
    for i in range(2, int(n ** (1 / 2)) + 1):
        if n % i != 0:
            continue
        num = 0
        while n % i == 0:
            num += 1
            n //= i
        primes.append([i, num])
    if n != 1:
        primes.append([n, 1])
    return primes

N = int(input())
A = list(map(int, input().split()))
# N = 10 ** 6
# A = [10 ** 6] * N
pairwise = False
prime_key = set(prime_factorize(A[-1]).keys())
break_flag = False
prime_flags = [False] * (10 ** 6 + 1)
for i in range(N):
    for key in prime_factorize(A[i]).keys():
        if prime_flags[key]:
            break_flag = True
            break
        else:
            prime_flags[key] = True
    if break_flag:
        break
else:
    pairwise = True
if pairwise:
    print('pairwise coprime')
    exit()
work = gcd(A[0], A[1])
for i in range(2, N):
    work = gcd(work, A[i])
if work != 1:
    print('not coprime')
else:
    print('setwise coprime')


### FIXED CODE ###

class prime_factorize_by_osa_k():
    def __init__(self, max_val):
        '''
        割ることが出来る最小の値を格納したリストを返す
        :param max_val:
        :return:
        '''
        self.minFactor = [-1] * (max_val + 1)
        for i in range(2, max_val + 1):
            if self.minFactor[i] == -1:
                self.minFactor[i] = i
                # エラトステネスの篩と同様の処理を行う
                for j in range(i * i, max_val + 1, i):
                    if self.minFactor[j] == -1:
                        self.minFactor[j] = i

    def osa_k(self, n):
        '''
        preprocessをしたあと、O(logN)で素因数分解を行う。nの最大値をn_maxとする。
        :param n:
        :return:
        '''
        from collections import defaultdict
        d = defaultdict(int)
        now = n
        while now > 1:
            d[self.minFactor[now]] += 1
            now //= self.minFactor[now]
        return d
def gcd(a, b):
    while b: a, b = b, a % b
    return a

N = int(input())
A = list(map(int, input().split()))
# N = 10 ** 6
# A = [10 ** 6] * N
ob = prime_factorize_by_osa_k(10 ** 6)
pairwise = False
prime_key = set(ob.osa_k(A[-1]).keys())
break_flag = False
prime_flags = [False] * (10 ** 6 + 1)
for i in range(N):
    for key in ob.osa_k(A[i]).keys():
        if prime_flags[key]:
            break_flag = True
            break
        else:
            prime_flags[key] = True
    if break_flag:
        break
else:
    pairwise = True
if pairwise:
    print('pairwise coprime')
    exit()
work = gcd(A[0], A[1])
for i in range(2, N):
    work = gcd(work, A[i])
if work != 1:
    print('not coprime')
else:
    print('setwise coprime')
a,b = map(double, raw_input().split())
int x,y
double z
x=a/b
y=a%b
z=a/b
print x y z

### FIXED CODE ###

a,b=map(int,raw_input().split())
print ('%d %d %f' % (a/b,a%b,float(a)/b))
result=[]
N = int(input())
W = list(map(int,input().split()))
for i in range(1:N+1):
  a = W[:i]
  b = W[i+1:N]
  c = sum(a)
  d = sum(b)
  e = abs(c-d)
  result.append(e)
 
print(min(result))

### FIXED CODE ###

N = int(input())
W = list(map(int, input().split()))
i = 0
W_sum = sum(W)
ans_l = []
tmp_l = 0
for i in range(N):
    tmp_l += W[i]
    if((W_sum-tmp_l) - tmp_l < 0):
        ans_l.append(-((W_sum-tmp_l) - tmp_l))
    else:
        ans_l.append((W_sum-tmp_l) - tmp_l)
print(min(ans_l))
import sys
import collections as c
sys.setrecursionlimit(10**6)

class UnionFind():
	def __init__(self, n):
		self.size = n
		self.root = [-1 for _ in range(n+1)]
		self.rnk = [0 for _ in range(n+1)]

	def findRoot(self, a):
		if self.root[a] < 0:
			return a
		else:
			return self.findRoot(self.root[a])

	def uniteTree(self, a, b):
		a = self.findRoot(a)
		b = self.findRoot(b)

		if a == b:
			return

		elif self.rnk[a] > self.rnk[b]:
			self.root[a] += self.root[b]
			self.root[b] = a

		elif self.rnk[b] > self.rnk[a]:
			self.root[b] += self.root[a]
			self.root[a] = b

		elif self.rnk[a] == self.rnk[b]:
			self.root[b] += self.rnk[a]
			self.root[a] = b
			self.rnk[b] += 1

	def judgeTree(self, a, b):
		return self.findRoot(a) == self.findRoot(b)

	def count(self, a):
		return self.rnk[self.findRoot(a)] * (-1)

N, K, L = map(int,input().split())
p = []
q = []
l = []
r = []

for _ in range(K):
	p_tmp, q_tmp = map(int ,input().split())
	p.append(p_tmp)
	q.append(q_tmp)

for _ in range(L):
	l_tmp, r_tmp = map(int, input().split())
	l.append(l_tmp)
	r.append(r_tmp)

road = UnionFind(N)
train = UnionFind(N)

for i in range(K):
	road.uniteTree(p[i], q[i])

for i in range(L):
	train.uniteTree(l[i], r[i])

ar = []

for i in range(1,N+1):
	a = road.findRoot(i)
	b = train.findRoot(i)
	ar.append(str([a,b]))

Car = c.Counter(ar)

for i in range(N):
	print(Car[ar[i]], end = " ")

### FIXED CODE ###

import sys
import collections as c
sys.setrecursionlimit(10**6)

import sys
sys.setrecursionlimit(10**7)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    def Count(self, x):
        return -self.root[self.Find_Root(x)]

N, K, L = map(int,input().split())
p = []
q = []
l = []
r = []

for _ in range(K):
	p_tmp, q_tmp = map(int ,input().split())
	p.append(p_tmp)
	q.append(q_tmp)

for _ in range(L):
	l_tmp, r_tmp = map(int, input().split())
	l.append(l_tmp)
	r.append(r_tmp)

road = UnionFind(N)
train = UnionFind(N)

for i in range(K):
	road.Unite(p[i], q[i])

for i in range(L):
	train.Unite(l[i], r[i])

ar = []

for i in range(1,N+1):
	a = road.Find_Root(i)
	b = train.Find_Root(i)
	ar.append(str([a,b]))

Car = c.Counter(ar)

for i in range(N):
	print(Car[ar[i]], end = " ")
from heapq import heappush, heappop


def dijkstra(graph: list, n: int, v_s: int, INF: int = float('inf')) -> list:
    # graph[v_from] = [(cost, v_to), ...]
    dist = [INF] * n

    dist[v_s] = 0
    heap = [(0, v_s)]  # heap = [(dist[v], v), ...]
    while heap:
        dist2v, v_from = heappop(heap)
        if dist[v_from] < dist2v:
            continue
        for cost, v_to in graph[v_from]:
            dist_cand = dist2v + cost
            if dist_cand < dist[v_to]:
                dist[v_to] = dist_cand
                heappush(heap, (dist[v_to], v_to))
    return dist


k = int(input())

graph = [[] for _ in range(k)]
for i in range(1, k):
    graph[i].append((1, i + 1))
    graph[i].append((0, 10 * i % k))

dist = dijkstra(graph, k, 1)
ans = dist[0] + 1
print(ans)


### FIXED CODE ###

from heapq import heappush, heappop


def dijkstra(graph: list, n: int, v_s: int, INF: int = float('inf')) -> list:
    # graph[v_from] = [(cost, v_to), ...]
    dist = [INF] * n

    dist[v_s] = 0
    heap = [(0, v_s)]  # heap = [(dist[v], v), ...]
    while heap:
        dist2v, v_from = heappop(heap)
        if dist[v_from] < dist2v:
            continue
        for cost, v_to in graph[v_from]:
            dist_cand = dist2v + cost
            if dist_cand < dist[v_to]:
                dist[v_to] = dist_cand
                heappush(heap, (dist[v_to], v_to))
    return dist


k = int(input())

graph = [[] for _ in range(k)]
for i in range(1, k):
    graph[i].append((1, (i + 1) % k))
    graph[i].append((0, 10 * i % k))

dist = dijkstra(graph, k, 1)
ans = dist[0] + 1
print(ans)
nx = list(map(int, input().split()))
ln = list(map(int, input().split()))
n = nx[0]
x = nx[1]

dn = 0
count = 1
for i in range(0, n+1, 1):
    dn += ln[i]
    if dn > x:
        break
    count += 1
print(count)

### FIXED CODE ###

nx = list(map(int, input().split()))
ln = list(map(int, input().split()))
n = nx[0]
x = nx[1]

dn = 0
count = 1
for i in range(0, n, 1):
    dn += ln[i]
    if dn > x:
        break
    count += 1
print(count)
import math
r=input()
print("{} {}".format(2*r*math.pi,r*r*math.pi))


### FIXED CODE ###

import math
pi=math.pi
r=float(input())
print("{:.5f} {:.5f}".format(r*r*pi,2*r*pi))
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

import collections
N = int(input())
A = list(map(int, input().split()))
cA = collections.Counter(A)

LIM = 10 ** 6 + 1
# LIM = 25

A.sort()
dp = [1] * LIM

for i in set(A):
    s = i * 2
    while s <= LIM:
        dp[s] = 0
        s += i

ans = 0
# print(dp)
for a in A:
    # print("{} {}".format(dp[a], cA[a]))
    if dp[a] and cA[a] == 1:
        # print(a)
        ans += 1
print(ans)

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

import collections
N = int(input())
A = list(map(int, input().split()))
cA = collections.Counter(A)

LIM = 10 ** 6 + 1
# LIM = 25

A.sort()
dp = [1] * LIM

for i in set(A):
    s = i * 2
    while s < LIM:
        dp[s] = 0
        s += i

ans = 0
# print(dp)
for a in A:
    # print("{} {}".format(dp[a], cA[a]))
    if dp[a] and cA[a] == 1:
        # print(a)
        ans += 1
print(ans)
n, m, k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

total = 0
count = 0
flag = len(a) - 1
for i in range(n):
    total += a[i]
    if total > k:
        total -= a[i]
        flag = i
        break
    count += 1
ans = count
for i in range(m):
    if b[i] > k:
        break
    total += b[i]
    count += 1
    while total > k:
        total -= a[flag]
        flag -= 1
        count -= 1
    ans = max(ans, count)

print(ans)

### FIXED CODE ###

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

total = 0
count = 0
flag = n-1
for i in range(n):
    total += a[i]
    if total > k:
        total -= a[i]
        flag = i-1
        break
    count += 1
ans = count
for i in range(m):
    if b[i] > k:
        break
    total += b[i]
    count += 1
    while total > k:
        if flag == -1:
            break
        else:
            total -= a[flag]
            flag -= 1
            count -= 1
    if total > k: 
        break
    ans = max(ans, count)

total = 0
count = 0
flag = m-1
for i in range(m):
    total += b[i]
    if total > k:
        total -= b[i]
        flag = i-1
        break
    count += 1
for i in range(n):
    if a[i] > k:
        break
    total += a[i]
    count += 1
    while total > k:
        if flag == -1:
            break
        else:
            total -= b[flag]
            flag -= 1
            count -= 1
    if total > k: 
        break
    ans = max(ans, count)


print(ans)
h,w,k = list(map(int,input().split()))
arr = [input() for _ in range(h)]

from itertools import product
import numpy as np
ans = [0] * (2**(h-1))
ans_index = 0

for horizontal_condition in product((True,False),repeat=h-1):
    count = np.zeros(h)
    divide = sum(horizontal_condition)
    trans_matrix = np.zeros((h,h))
    trans_matrix[0,0] = 1
    down = 0
    right = 0
    
    for i in horizontal_condition:
        if i:
            down += 1
        right += 1
        trans_matrix[down,right] = 1
        
    for vertical_divide in range(w):
        tmparr = np.array([int(i[vertical_divide]) for i in arr])
        addarr = np.dot(trans_matrix,tmparr)
        if max(count+addarr) > k:
            count = addarr
            divide += 1
        else:
            count += addarr
            
    ans[ans_index] = divide
    ans_index += 1
    
print(min(ans))

### FIXED CODE ###

h,w,k = list(map(int,input().split()))
arr = [[int(i) for i in input()] for _ in range(h)]

from itertools import product
ans = 2000

for idx,cond in enumerate(product((True,False),repeat=h-1)):
    div = sum(cond)
    spl = [arr[0][:]]
    for i in range(h-1):
        if cond[i]:
            spl.append(arr[i+1][:])
        else:
            spl[-1] = [spl[-1][j] + arr[i+1][j] for j in range(w)]
    num = len(spl)
    cnt = [0]*num
    
    for v in range(w):
        tmp = [spl[i][v] for i in range(num)]
        if max(tmp) > k:
            break
        if max([cnt[i] + tmp[i] for i in range(num)]) > k:
            div += 1
            cnt = tmp[:]
        else:
            cnt  = [cnt[i] + tmp[i] for i in range(num)]
    else:    
        ans = min(ans,div)
            
print(ans)
a, b, k = map(int, input().split())
da = []
db = []
dc = []
for i in range(1,a+1):
    if a%i == 0:
    	da.append(i)

for j in range(1, b+1):
    if b%j == 0:
    	db.append(j)

for k in da:
    if k in db:
    	dc.append(k)

dc.sort(reverse = True)
print(dc[k])


### FIXED CODE ###

a, b, k = map(int, input().split())
da = []
db = []
dc = []
for i in range(1,a+1):
    if a%i == 0:
    	da.append(i)

for j in range(1, b+1):
    if b%j == 0:
    	db.append(j)

for l in da:
    if l in db:
    	dc.append(l)

dc.sort(reverse = True)
print(dc[k-1])
N=int(input())
if N==1:
  print(33)
  quit()
G=[[] for i in range(N)]
res=[0]*N
def dfs(v,p,c):
  res[v]=c
  for nv,w in G[v]:
    if nv==p:
      continue
    if (w & 1):
      dfs(nv,v,1-c)
    else:
      dfs(nv,v,c)

for i in range(N-1):
  u,v,w=map(int,input().split())
  u-=1
  v-=1
  G[u].append((v,w))
  G[v].append((u,w))
dfs(0,-1,0)
for i in range(N):
  print(res[i])

### FIXED CODE ###

N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    u,v,w=map(int,input().split())
    u,v=u-1,v-1
    G[u].append((v,w))
    G[v].append((u,w))
reached=[0]*N
stack=[0]
reached[0]=[1]
res=[-1]*N
res[0]=0
while(stack):
    v=stack.pop()
    for nv,w in G[v]:
        if reached[nv]:
            continue
        if w & 1:
            res[nv]=1-res[v]
        else:
            res[nv]=res[v]
        stack.append(nv)
        reached[nv]=1
for i in res:
    print(i)
import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 2
5 1 4
2 3
1 5"""
        output = """14"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4"""
        output = """338"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """3 2
100 100 100
3 99
3 99"""
        output = """300"""
        self.assertIO(input, output)
    def test_入力例_4(self):
        input = """11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000"""
        output = """10000000001"""
        self.assertIO(input, output)

def resolve():
    (N,M)=(int(i) for i in input().split())
    A=[int(i) for i in input().split()]
    A.sort()
    BC=[[int(i) for i in input().split()] for i in range(M)]
    BC.sort(key=lambda x: x[1] , reverse=True)
    fst=0
    for i in BC:
        cnt=i[0]
        val=i[1]
        while  cnt>0:
            if A[fst]<val:
                A[fst]=val
                cnt-=1
                fst+=1
            else:
                break
        else:
            continue
        break
    print(sum(A))



if __name__ == "__main__":
    resolve()

### FIXED CODE ###

import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 2
5 1 4
2 3
1 5"""
        output = """14"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4"""
        output = """338"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """3 2
100 100 100
3 99
3 99"""
        output = """300"""
        self.assertIO(input, output)
    def test_入力例_4(self):
        input = """11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000"""
        output = """10000000001"""
        self.assertIO(input, output)

def resolve():
    (N,M)=(int(i) for i in input().split())
    A=[int(i) for i in input().split()]
    A.sort()
    BC=[[int(i) for i in input().split()] for i in range(M)]
    BC.sort(key=lambda x: x[1] , reverse=True)
    fst=0
    for i in BC:
        cnt=i[0]
        val=i[1]
        while  cnt>0:
            if fst>=N:
                break
            if A[fst]<val:
                A[fst]=val
                cnt-=1
                fst+=1
            else:
                break
        else:
            continue
        break
    print(sum(A))



if __name__ == "__main__":
    resolve()
a, b =  map(int,input().split())
c = A + B
if c < A - B:
	c = A - B
if c < A * B:
	c = A * B
print(c)

### FIXED CODE ###

a, b =  map(int,input().split())
c = a + b
if c < a - b:
	c = a - b
if c < a * b:
	c = a * b
print(c)
N, X = map(int, input().split())

a = [1]
p = [1]
for i in range(1, N+1):
    a.append(2 * a[i-1] + 3)
    p.append(2 * a[i-1] + 1)

def calc(N, X): #レベルNバーガーの下からX層に含まれるパティの枚数
    if N == 0: #全てパティ
        if X == 0:
            return 0
        else:
            return 1
    if X == 1:
        return 0
    # print (N - 1)
    if 1 <= X <= a[N - 1]:
        # print ('A')
        return calc(N - 1, X - 1)
    if X == 2 + a[N - 1]:
        # print ('B')
        return p[N - 1] + 1
    if 2 +a[N - 1] < X <= 2 + 2 * a[N - 1]:
        # print ('C')
        return p[N - 1] + 1 + calc(N - 1, X - 2 - a[N - 1])
    if X == 3 + 2 * 2 * a[N - 1]:
        # print ('D')
        return 2 * p[N - 1] + 1

print (calc(N, X))

### FIXED CODE ###

D = int(input())
print ('Christmas', end = '')
for i in range(25 - D):
    print (' Eve', end = '')
print ()
sm=sum(n)
av = sm/2
c =0

for i in range(len(n)):
	c += n[i]
	if c == av:
		print(0)
		exit()
	elif c > av:
		b1 = abs(c - (sm-c))
		b2 = abs((c-n[i]) - (sm-c+n[i]))
		print(b1 if b1<b2 else b2)
		exit()	


### FIXED CODE ###

N = int(input())
n = list(map(int, input().split()))
sm=sum(n)
av = sm/2
c =0

for i in range(N):
	c += n[i]
	if c == av:
		print(0)
		exit()
	elif c > av:
		b1 = abs(c - (sm-c))
		b2 = abs((c-n[i]) - (sm-c+n[i]))
		print(b1 if b1<b2 else b2)
		exit()
n=int(input())
p=n//2
l=list(map(int,input().split()))
for i in range(n):
    m=l
    m.pop(i)
    m.sort()
    print(m[p-1])

### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
l=sorted(x)
m1=l[n//2-1]
m2=l[n//2]
for i in range(n):
    if x[i]<=m1:
        print(m2)
    else:
        print(m1)
A,B=map(int,input().split())


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

print(lcm(A,B))

### FIXED CODE ###

import fractions

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


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

print(lcm(A,B))
from functools import lru_cache
import sys
sys.setrecursionlimit(2147483647)

N = int(input())
A = []
for i in range(0,N):
    A.append(list(map(int,input().split())))



@lru_cache(None)
def dfs(d,pre):
    if d>=N-1: return 0
    tmp = [0] 
    for idx,a in enumerate(A[d]):
        if idx != pre:
            res = dfs(d + 1,idx) + a 
            tmp.append(res)
    return max(tmp)

print(dfs(-1,-1))

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int, input().split()))
dp = [0 for _ in range(len(A))]
dp[0] = 0 
for i in range(1,N):
    tmp = [float("inf")]
    for j in range(1,K+1):
        if i - j>=0:
            tmp.append(dp[i-j] + abs(A[i] - A[i-j]))
    dp[i] = min(tmp)

print(dp[len(A)-1])
N = int(input())
list = [int(a) for a in input().split()]

A = sum(list)//N

for i in range(-100:100):
    sum = (list[i] - A) ** 2
    sum_new = (list[i] - i) ** 2
    if(sum > sum_new):
        sum = sum_new
print(sum)


### FIXED CODE ###


N = int(input())
list = [int(a) for a in input().split()]

A = sum(list)//N
ans = 0

for k in range(N):
    ans = ans + (list[k] - A) ** 2

for i in range(-100,100):
    sum_new = 0
    for j in range(N):
        sum_new = sum_new + (list[j] - i) ** 2
    if(ans > sum_new):
        ans = sum_new

print(ans)
n = int(input())
nn = n = int(input())
if n == nn:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n, nn = map(int, input().split())
if n == nn:
  print("Yes")
else:
  print("No")
N, W = map(int, input().split())

MAX_V = N * (10 ** 3)
wv = [list(map(int, input().split())) for _ in range(N)]
dp = [10**9+7 for _ in range(MAX_V + 1)]
dp[0] = 0

for w, v in range(N):
    for j in range(MAX_V + 1):
        if j - v >= 0:
            dp[j] = min(dp[j],dp[j - v] + w)
        else:
            dp[j] = dp[j]

mv = 0
for i in range(MAX_V + 1):
    if dp[i] <= W:
        mv = i

print(mv)


### FIXED CODE ###

N, W = map(int, input().split())

MAX_V = N * (10 ** 3)
w, v = [], []
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

dp = [[10**9+7 for _ in range(MAX_V + 1)] for _ in range(N + 1)]
dp[0][0] = 0

for i in range(N):
    for j in range(MAX_V + 1):
        if j - v[i] >= 0:
            dp[i + 1][j] = min(dp[i][j],dp[i][j - v[i]] + w[i])
        else:
            dp[i + 1][j] = dp[i][j]

mv = 0
for i in range(MAX_V + 1):
    if dp[N][i] <= W:
        mv = i
print(mv)
p = 1
for i in range(n):
  p = p*(i+1)%(10**9+7)
print(p)

### FIXED CODE ###

p = 1
for i in range(int(input())):
  p = p*(i+1)%(10**9+7)
print(p)
x, y = map(int,input().split())
     
    for i in range(x+1):
        if 4 * i + 2*(x - i) == y:
            print('Yes')
            exit()
     
    print('No')

### FIXED CODE ###

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

for i in range(x + 1):
    if 4 * i + 2 * (x - i) == y:
        print('Yes')
        exit()

print('No')
from sys import stdin
N=(stdin.readline().rstrip())
if sum(list(map(int,list(N)))) % N == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

from sys import stdin
N=(stdin.readline().rstrip())
if int(N) % sum(list(map(int,list(N)))) == 0:
    print("Yes")
else:
    print("No")
#KyoproRの競技プログラミング過去問配信
S = input()
k = []
b = ["A","C","G","T"]
a = 0
for i in range(len(S)):
    #len(S)の間roop
    #S[i]が"A" "C" "G" "T"のいずれかであるかを判定
    if S[i] in b:
        if i == len(S)-1:
            k.append(1)
            break
        else:
            for j in range(len(S)-1):
                if S[i+j] in b:
                    a += 1
                else:
                    k.append(a)
                    a = 0
                    break
if len(k) == 0:
    print(0)
else:
    print(max(k))

### FIXED CODE ###

S = input()
mode = 0
now = 0
k = []
for i in range(len(S)):
    if str(S[i]) == "A" or str(S[i]) == "T" or str(S[i]) == "G" or str(S[i]) == "C":
        if mode == 0:
            mode = 1
            now += 1
        else:
            now += 1
    else:
        k.append(now)
        now = 0
        mode = 0
k.append(now)
if len(k) == 0:
    print(0)
else:
    print(max(k))
n,l = map(int,input().split())
s = input() for i in range(n)
print(*stored(s),sep="")


### FIXED CODE ###

n,l = map(int,input().split())
s = [input() for i in range(n)]
print(*sorted(s),sep="")