Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

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

l = []
for i in range(N):
	w, v = list(map(int, input().split(" ")))
	l.append((w, v))

def dp(i, score, remaining_weight):
	if (i < 0):
		return score
	if remaining_weight >= l[i][0]:
		# on / off
		return max([dp(i - 1, score + l[i][1], remaining_weight - l[i][0]), dp(i - 1, score, remaining_weight)])
	else:
		return dp(i-1, score, remaining_weight)

print(dp(N-1, 0, W))

### FIXED CODE ###

N, W = list(map(int, input().split(" ")))
dp =  [[0] * (W+1) for _ in range(N+1)]
 
for i in range(0, N):
	weight, value = map(int, input().split(" "))
	for w in range(1, W+1):
		if w >= weight:
			dp[i + 1][w] = max([dp[i][w - weight] + value, dp[i][w]])
		else:
			dp[i + 1][w] = dp[i][w]
print(dp[N][W])
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy
from operator import itemgetter

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, K = na()
ans = 0
if K == 0:
    print(N ** 2)
    sys.exit()
    
for b in range(K+1, N+1):
    #print(b)
    for q in range(K, b):
        ans += (N - q) // b + 1
print(ans)


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy
from operator import itemgetter

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

#解説みた
N, K = na()
ans = 0
for b in range(1, N+1):
    p = N // b
    r = N % b
    ans += p * max(0, b - K)
    ans += max(0, r - K + 1)

if K == 0:
    ans -= N
print(ans)
### BUGGY CODE ###

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

edges = [[] for _ in range(n)]

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

q = [0]

ans = [-1]*n
ans[0] = 0
count = 1

while q:
    l = q.pop(0)
    for i in edges[l]:
        if ans[i] == -1:
            ans[i] = l
            count += 1
            q.append(i)
    if count == n:
        break

if count == n:
    print('Yes')
    for i in ans[1:]:
        print(i+1)
else:
    print('No')


### FIXED CODE ###

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

edges = [[] for _ in range(n)]

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

q = [0]

ans = [-1]*n
ans[0] = 0
count = 1

while q:
    l = q.pop(0)
    for i in edges[l]:
        if ans[i] == -1:
            ans[i] = l
            count += 1
            q.append(i)
    if count == n:
        break

if count == n:
    print('Yes')
    for i in ans[1:]:
        print(i+1)
else:
    print('No')
### BUGGY CODE ###

import math
a,b,n = map(int,input().split())
max = 0
x = 0
while math.floor(a*x/b) - a*math.floor(x/b) <= a and x <= n:
	if max < math.floor(a*x/b) - a*math.floor(x/b):
		max = math.floor(a*x/b) - a*math.floor(x/b)
	x += 1
print(max)

### FIXED CODE ###

import math
a,b,n = map(int,input().split())
if n >= b-1:
	print(math.floor(a*(b-1)/b) - a*math.floor((b-1)/b))
else:
	print(math.floor(a*n/b) - a*math.floor(n/b))
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,q = inpl()
g = [[]for i in range(n)]
c = [0 for i in range(n)]
seen = [False] * n
for i in range(n-1):
    a,b = inpl()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
for i in range(q):
    a,b = inpl()
    c[a-1] += b
def dfs(node):
    for v in g[node]:
        if seen[v]:
            continue
        c[v] += c[node]
        seen[v] = True
        dfs(v) 
seen[0] = True
dfs(0)
print(*c)


### FIXED CODE ###

n,q = map(int,input().split())
ki = [0] * (n+1)
c = [0] * (n+1)
for i in range(n-1):
    a,b = map(int,input().split())
    ki[b] = a
for i in range(q):
    p,x = map(int,input().split())
    c[p] += x

for i in range(2,n+1):
    c[i] += c[ki[i]]
print(*c[1:])
### BUGGY CODE ###

def solve(A, m):
	if m == 0:
		return True
	if m<0 or len(A)==0:
		return False
	else:
		no_use = solve(A[1:], m-int(A[0]))
		if no_use:
			return True
		else:
			return (solve(A[1:], m))

def main():
	n = int(input())
	A = input()
	A = A.split()
	q = int(input())
	ms= input()
	for m in ms.split():
		if solve(A, int(m)):
			print('yes')
		else:
			print('no')

if __name__ == '__main__':
	main()

### FIXED CODE ###

def power_set(A, s):
	if len(A) == 0:
		return {s}
	else:
		return power_set(A[1:], s) | power_set(A[1:], s+A[0])

def main():
	n = int(input())
	A = input()
	#print(n)
	A = list(map(int, A.split()))
	q = int(input())
	m = input()
	ms = list(map(int, m.split()))
	powerset = power_set(A, 0)
	
	for m in ms:
		if m in powerset:
			print('yes')
		else:
			print('no')

if __name__ == '__main__':
	main()
### BUGGY CODE ###

import sys

input = sys.stdin.readline
N, M = map(int, input().split())
AB = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[1])[::-1]
plan = [0] * (M+1)
ans = 0
for a, b in AB:
    i = a
    while i < (M+1) and plan[i] == 1:
        i += 1
    if i < (M+1):
        plan[i] = 1
        ans += b
print(ans)


### FIXED CODE ###

import sys

input = sys.stdin.readline
N, M = map(int, input().split())
AB = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[1])[::-1]
plan = [i for i in range(M+1)]
ans = 0
for a, b in AB:
    i = a
    while i < (M + 1) and plan[i] != i:
        plan[i] += 1
        i = plan[i] -1
    if i < (M+1):
        plan[i] += 1
        ans += b
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
list1 = [list(map(int,input().split())) for i in range(m)]

list2 = [[] for i in range(n)]
#int型
def zeropadding(s):
    padding = 6 #何桁揃えにするか入力
    return ("{0:0"+str(padding)+"d}").format(s)
    #returnはstr型なので注意！

for i in range(m):
    list2[list1[i][0]-1].append(list1[i][1])
for i in range(n):
    list2[i].sort()

for i in range(m):
    print(zeropadding(list1[i][0])+zeropadding(list2[list1[i][0]-1].index(list1[i][1])+1))

### FIXED CODE ###

from copy import deepcopy as dp
from operator import itemgetter as ig
n,m = map(int,input().split())
#[input番号,県番号,年,県における順番]
list1 = []
for i in range(m):
    list1.append([i] + list(map(int,input().split())))

list2 = dp(list1)
list2.sort(key=ig(1,2))
city_number = 0
list2[0].append(city_number)
for i in range(1,m):
    if list2[i][1] == list2[i-1][1]:
        city_number += 1
        list2[i].append(city_number)
    else:
        city_number = 0
        list2[i].append(city_number)
list2.sort(key=ig(0))
for i in range(m):
    print("{0:06d}".format(list2[i][1])+"{0:06d}".format(list2[i][3]+1))
### BUGGY CODE ###

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

mod = 1000000007

def nCr(n, r):

    r = min(r, n-r)

    bunsi = 1
    for i in range(n, n-r, -1):
        bunsi *= i

    bunbo = 1
    for i in range(r, 1, -1):
        bunbo *= i

    return bunsi // bunbo


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

hana_kind_cnt = n

result = 0
for hanataba_koho_select_cnt in range(1, hana_kind_cnt + 1):
    if not(hanataba_koho_select_cnt == a or hanataba_koho_select_cnt == b):
        result += nCr(n, hanataba_koho_select_cnt) % mod

print(int(result))


### FIXED CODE ###

# -*- coding: utf-8 -*-
from functools import reduce

MOD = 1000000007

def power_func(a, b, mod):
    if b == 0: return 1
    if b % 2 == 0:
        d = power_func(a, b // 2, mod)
        return d * d % mod
    if b % 2 == 1:
        return (a * power_func(a, b - 1, mod)) % mod

def nCr(n, r, mod):

    min_r = min(r, n-r)

    if min_r == 1: return n


    bunsi = reduce(lambda x, y: (x * y) % mod, range(n, n-r, -1))
    bunbo = reduce(lambda x, y: (x * y) % mod, range(r, 1, -1))

    return bunsi * power_func(bunbo, mod - 2, mod) % mod


n, a, b = [int(i) for i in input().split()]

print(((power_func(2, n, MOD) -1) - nCr(n, a, MOD)- nCr(n, b, MOD)) % MOD)
### BUGGY CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n, *a = map(int, read().split())
    if n == 1:
        print(1)
        sys.exit()
    if n == 2:
        if a[0] == a[1]:
            print(0)
            sys.exit()
        elif max(a) % min(a) == 0:
            print(0)
            sys.exit()
        else:
            print(2)
            sys.exit()
    a.sort()
    notdiv = [True] * n
    for i1, ae in enumerate(a):
        if notdiv[i1]:
            t = ae * 2
            while t <= max(a):
                if t in a:
                    notdiv[a.index(t)] = False
                t += ae
    if a[0] == a[1]:
        notdiv[0] = False
    if a[-1] == a[-2]:
        notdiv[-1] = False
    for j1 in range(1, n - 1):
        if a[j1-1] == a[j1] or a[j1] == a[j1+1]:
            notdiv[j1] = False
    r = sum(notdiv)
    print(r)
if __name__ == '__main__':
    main()

### FIXED CODE ###

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

    a.sort()
    tf = [0] * (a[-1] + 1)
    for ea in a:
        tf[ea] = 1
    for i1 in range(n - 1):
        if a[i1] == a[i1 + 1]:
            tf[a[i1]] = 0

        for i2 in range(2, a[-1]//a[i1] + 1):
            tf[a[i1] * i2] = 0
    r = sum(tf)
    print(r)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import deque
from typing import List
 
 
def main():
    h, w = map(int, input().split())
    g = []
    for _ in range(h):
        r = input()
        g.append(r)
    print(mm(h, w, g))
 
 
def mm(h: int, w: int, g: List[List[str]]) -> int:
    ret = 0
    for i in range(h):
        for j in range(w):
            if (g[i][j] == '#'):
                continue
            q = deque([(i, j, 0)])
            v = set()
            while q:
                ii, jj, cnt = q.popleft()
                v.add((ii, jj))
                ret = max(ret, cnt)
                # ↓
                if ii < h - 1 and g[ii + 1][jj] == '.' and (ii + 1, jj) not in v:
                    q.append((ii + 1, jj, cnt + 1))
                # →
                if jj < w - 1 and g[ii][jj + 1] == '.' and (ii, jj + 1) not in v:
                    q.append((ii, jj + 1, cnt + 1))
                # ↑
                if ii > 0 and g[ii - 1][jj] == '.' and (ii - 1, jj) not in v:
                    q.append((ii - 1, jj, cnt + 1))
                # ←
                if jj > 0 and g[ii][jj - 1] == '.' and (ii, jj - 1) not in v:
                    q.append((ii, jj - 1, cnt + 1))
    return ret
 
 
if __name__ == '__main__':
    main()


### FIXED CODE ###

import queue


def get_longest(s_tmx, i, j, h, w):
    q = queue.Queue()
    q.put((i, j))
    dist_mtx = [[-1] * w for a in range(h)]
    dist_mtx[i][j] = 0
    while not q.empty():
        pnt = q.get()
        y = pnt[0]
        x = pnt[1]
        if x - 1 >= 0 and dist_mtx[y][x-1] == -1 and s_mtx[y][x-1] == 1:
            dist_mtx[y][x-1] = dist_mtx[y][x] + 1
            q.put((y, x-1))
        if y - 1 >= 0 and dist_mtx[y-1][x] == -1 and s_mtx[y-1][x] == 1:
            dist_mtx[y-1][x] = dist_mtx[y][x] + 1
            q.put((y-1, x))
        if x < w - 1 and dist_mtx[y][x+1] == -1 and s_mtx[y][x+1] == 1:
            dist_mtx[y][x+1] = dist_mtx[y][x] + 1
            q.put((y, x+1))
        if y < h - 1 and dist_mtx[y+1][x] == -1 and s_mtx[y+1][x] == 1:
            dist_mtx[y+1][x] = dist_mtx[y][x] + 1
            q.put((y+1, x))
    ret = 0
    for item in dist_mtx:
        for item_item in item:
            if item_item > ret:
                ret = item_item
    return ret


h, w = map(int, input().split())
s_mtx = []

for i in range(h):
    s_list = [0] * w
    tmp = input()
    for j in range(len(tmp)):
        if tmp[j] == ".":
            s_list[j] = 1
        else:
            s_list[j] = 0
    s_mtx.append(s_list)

ret = 0

for i in range(h):
    for j in range(w):
        if s_mtx[i][j] == 1:
            tmp = get_longest(s_mtx, i, j, h, w)
            if tmp > ret:
                ret = tmp

print(ret)
### BUGGY CODE ###

N, X, Y = list(map(int, input().split()))

# N = 7
# X = 3
# Y = 7

ans = [0]*N

for sv in range(N):
    # dist[v] = dist from sv to v
    dist = [float("inf")]*N
    last_visited = []
    dist[sv] = 0
    last_visited.append(sv)
    while last_visited:
        next_last_visited = []
        for v in last_visited:
            if v+1 < N and dist[v+1] == float("inf"):
                dist[v+1] = dist[v]+1
                next_last_visited.append(v+1)
            if v-1 >= 0 and dist[v-1] == float("inf"):
                dist[v-1] = dist[v]+1
                next_last_visited.append(v-1)
            if v == X-1 and dist[Y-1] == float("inf"):
                dist[Y-1] = dist[v]+1
                next_last_visited.append(Y-1)
            if v == Y-1 and dist[X-1] == float("inf"):
                dist[X-1] = dist[v]+1
                next_last_visited.append(X-1)
        # print(last_visited, next_last_visited)
        last_visited = next_last_visited
    # print(dist)
    for d in dist:
        ans[d] += 1

for a in ans[1:]:
    print(a//2)


### FIXED CODE ###


N, X, Y = list(map(int, input().split()))

# N = 2000
# X = 100
# Y = 1900


X -= 1
Y -= 1

# @profile


def main(N, X, Y):
    ans = [0]*N
    for i in range(N):
        for j in range(i+1, N):
            d = min(j-i, abs(X-i)+abs(Y-j)+1)
            ans[d] += 1

    for a in ans[1:]:
        print(a)


main(N, X, Y)
### BUGGY CODE ###

from collections import defaultdict

S = input()
T = input()

AS = defaultdict(list)
AT = defaultdict(list)

for i in range(len(S)):
    AS[S[i]].append(i)
    AT[T[i]].append(i)
    
isok = True
for i in range(len(S)):
    if AS[S[i]]!=AT[T[i]]:
        isok = False
        break
        
if isok:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

from collections import defaultdict

S = input()
T = input()

A = {}
B = {}

isok = True
for i in range(len(S)):
    if S[i] in A:
        if T[i] != A[S[i]]:
            isok = False
            break
    else:
        A[S[i]] = T[i]
    if T[i] in B:
        if S[i] != B[T[i]]:
            isok = False
            break
    else:
        B[T[i]] = S[i]
        
if isok:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

n=int(input())
for i in range(1,3501):
  for j in range(1,3501):
    if (4*i*j-n*i-n*j)!=0:
      if (n*i*j)%(4*i*j-n*i-n*j)==0 and (n*i*j)//(4*i*j-n*i-n*j)>0:
        k=(n*i*j)//(4*i*j-n*i-n*j)
        break
  else:
    continue
  break
print(i,j,k)

### FIXED CODE ###

n=int(input())
for i in range(1,3501):
  for j in range(1,3501):
    if (4*i*j-n*i-n*j)!=0:
      if (n*i*j)%(4*i*j-n*i-n*j)==0 and (n*i*j)//(4*i*j-n*i-n*j)>0:
        k=(n*i*j)//(4*i*j-n*i-n*j)
        break
  else:
    continue
  break
print(i,j,k)
### BUGGY CODE ###

"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
"""

from __future__ import division
from sys import stdin, maxint

def lcs(s1, s2):
	dp = [[0 for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]

	for i in xrange(1, len(s1) + 1):
		for j in xrange(1, len(s2) + 1):
			if s1[i - 1] == s2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

	return dp[len(s1)][len(s2)]

if __name__ == '__main__':
	tc = int(stdin.readline())
	for _ in range(tc):
		sa = stdin.readline().strip()
		sb = stdin.readline().strip()
		print(lcs(sa, sb))

### FIXED CODE ###

"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
"""


def lcs():
	s1 = raw_input()
	s2 = raw_input()
	la, lb = len(s1), len(s2)
	dp1 = [0 for _ in range(lb + 1)]

	for i in range(la):
		dp2 = dp1 + []
		for j in range(lb):
			if s1[i] == s2[j]:
				dp1[j + 1] = dp2[j] + 1
			elif dp1[j + 1] < dp1[j]:
				dp1[j + 1] = dp1[j]

	return dp1[-1]

if __name__ == '__main__':
	tc = int(raw_input())
	for _ in range(tc):
		print(lcs())
### BUGGY CODE ###

from collections import*
n = int(input())
c = Counter(map(int, input().split()))
s = set()
for i in c:
    c[i] -= 1
    for j in range(i, 10**6+1, i):
        if c[j]:
            s.add(j)
    c[i] += 1
r = 0
for i in c:
    r += c[i] * (i not in s)
print(r)

### FIXED CODE ###

from collections import*
n = int(input())
c = Counter(map(int, input().split()))
s = set()
for i in c:
    c[i] -= 1
    for j in range(i, 10**6+1, i):
        if c[j]:
            s.add(j)
    c[i] += 1
r = 0
for i in c:
    r += c[i] * (i not in s)
print(r)
### BUGGY CODE ###

N = int(input())
T = []
A = []

for _ in range(N):
    t, a = list(map(int, input().split()))
    T.append(t)
    A.append(a)

t_num = 1
a_num = 1
for i in range(N):
    # TAは常にn倍ずつ増加していく
    n = 1
    while T[i] * n < t_num or A[i] * n < a_num:
        n += 1
    t_num = T[i] * n
    a_num = A[i] * n

print(t_num + a_num)


### FIXED CODE ###

from math import ceil

N = int(input())
T = []
A = []

for _ in range(N):
    t, a = list(map(int, input().split()))
    T.append(t)
    A.append(a)

t_num = T[0]
a_num = A[0]
for i in range(1, N):
    tn = (t_num + T[i] - 1) // T[i]
    an = (a_num + A[i] - 1) // A[i]
    n = max(tn, an)
    t_num = T[i] * n
    a_num = A[i] * n

print(t_num + a_num)
### BUGGY CODE ###

X, Y, A, B, C = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
tmp = 0
p.sort(reverse=True)
p.append(0)
q.sort(reverse=True)
q.append(0)
r.sort(reverse=True)
r.append(0)
z = X+Y
for i in range(z):
    if X>0 and ((p[0]>=q[0] and p[0]>=r[0]) or (Y==0 and p[0]>=r[0])):
        tmp = tmp+p[0]
        p.pop(0)
        X -= 1
    elif Y>0 and ((q[0]>=p[0] and q[0]>=r[0]) or (X==0 and q[0]>=r[0])):
        tmp = tmp+q[0]
        q.pop(0)
        Y -= 1
    elif r[0]>p[0] or r[0]>q[0]:
        tmp = tmp+r[0]
        r.pop(0)
        
print(tmp)

### FIXED CODE ###

X, Y, A, B, C = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
tmp = 0
p.sort(reverse=True)
p.append(0)
q.sort(reverse=True)
q.append(0)
r.sort(reverse=True)
r.append(0)
z = X+Y
e, f, g = 0, 0, 0
for i in range(z):
    if X>0 and ((p[e]>=q[f] and p[e]>=r[g]) or (Y==0 and p[e]>=r[g])):
        tmp = tmp+p[e]
        e += 1
        X -= 1
    elif Y>0 and ((q[f]>=p[e] and q[f]>=r[g]) or (X==0 and q[f]>=r[g])):
        tmp = tmp+q[f]
        f += 1
        Y -= 1
    elif r[g]>p[e] or r[g]>q[f]:
        tmp = tmp+r[g]
        g += 1
        
print(tmp)
### BUGGY CODE ###

import io
import os

from collections import Counter, defaultdict, deque


from functools import lru_cache
import sys

sys.setrecursionlimit(10 ** 5)


def solve(N, A):
    def maxProfitAtEnd(i, money, stocks):
        if i == N - 1:
            # Sell all remaining
            return money + stocks * A[i]

        # no op
        best = maxProfitAtEnd(i + 1, money, stocks)
        """
        # TLE
        # sell
        for numStock in range(1, stocks + 1):
            best = max(
                best, maxProfitAtEnd(i + 1, money + numStock * A[i], stocks - numStock)
            )
        # buy
        for numStock in range(1, (money // A[i]) + 1):
            best = max(
                best, maxProfitAtEnd(i + 1, money - numStock * A[i], stocks + numStock)
            )

        """
        # sell
        best = max(best, maxProfitAtEnd(i + 1, money + stocks * A[i], 0))
        # buy
        numStock = money // A[i]
        best = max(
            best, maxProfitAtEnd(i + 1, money - numStock * A[i], stocks + numStock)
        )

        return best

    return maxProfitAtEnd(0, 1000, 0)


if __name__ == "__main__":
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    (N,) = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    ans = solve(N, A)
    print(ans)


### FIXED CODE ###

import io
import os

from collections import Counter, defaultdict, deque


from functools import lru_cache
import sys

sys.setrecursionlimit(10 ** 5)


def solve(N, A):
    @lru_cache(maxsize=None)
    def maxProfitAtEnd(i, money, stocks):
        if i == N - 1:
            # Sell all remaining
            return money + stocks * A[i]

        # no op
        best = maxProfitAtEnd(i + 1, money, stocks)
        # sell
        best = max(best, maxProfitAtEnd(i + 1, money + stocks * A[i], 0))
        # buy
        numStock = money // A[i]
        best = max(
            best, maxProfitAtEnd(i + 1, money - numStock * A[i], stocks + numStock)
        )

        return best

    return maxProfitAtEnd(0, 1000, 0)


def solve(N, A):
    money = 1000
    stock = 0
    for i in range(N - 1):
        if A[i] < A[i + 1]:
            # Buy on i
            numStock = money // A[i]
            money -= numStock * A[i]
            stock += numStock
            # Sell on i + 1
            money += stock * A[i + 1]
            stock = 0
    assert stock == 0
    return money


if __name__ == "__main__":
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    (N,) = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    ans = solve(N, A)
    print(ans)
### BUGGY CODE ###


from sys import stdin
from collections import deque


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    ipt = [[int(y) for y in x.rstrip().split()] for x in stdin.readlines()]
    MOD = 100100100100100100

    pl = [0] * (N + 1)

    for a, b in ipt:
        if pl[a] == 0:
            pl[a] = [b]
        else:
            pl[a].append(b)
        if pl[b] == 0:
            pl[b] = [a]
        else:
            pl[b].append(a)

    que = deque([1])
    deep = [MOD] * (N + 1)
    deep[1] = 0
    deep[0] = 0
    arrow = [0] * (N + 1)
    cnt = 1

    while not not que:
        q = que.popleft()
        tmp = False
        for i in pl[q]:
            if deep[i] != MOD:
                continue
            deep[i] = deep[q] + 1
            arrow[i] = q
            tmp = True
            cnt += 1
        if tmp:
            que.extend(pl[q])

    if N != cnt:
        print("No")
    else:
        print("Yes")
        for i in arrow[2:]:
            print(i)


if __name__ == "__main__":
    main()


### FIXED CODE ###


from sys import stdin
from collections import deque


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    ipt = [[int(y) for y in x.rstrip().split()] for x in stdin.readlines()]
    MOD = 100100100100100100

    pl = [0] * (N + 1)

    for a, b in ipt:
        if pl[a] == 0:
            pl[a] = [b]
        else:
            pl[a].append(b)
        if pl[b] == 0:
            pl[b] = [a]
        else:
            pl[b].append(a)

    que = deque([1])
    deep = [MOD] * (N + 1)
    deep[1] = 0
    deep[0] = 0
    arrow = [0] * (N + 1)
    cnt = 1

    while not not que:
        q = que.popleft()
        for i in pl[q]:
            if deep[i] != MOD:
                continue
            deep[i] = deep[q] + 1
            arrow[i] = q
            cnt += 1
            que.append(i)

    if N != cnt:
        print("No")
    else:
        print("Yes")
        for i in arrow[2:]:
            print(i)


if __name__ == "__main__":
    main()