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

import networkx as nx
n,m=map(int,input().split())
s=[list(map(int,input().split())) for i in range(m)]

g=nx.Graph()
g.add_nodes_from([i for i in range(1,n+1)])

for x in s:
    g.add_edge(x[0],x[1])
di=nx.predecessor(g,source=1)

if len(di)!=n:
    print("No")
    exit()

print("Yes")
for x in range(2,n+1):
    print(di[x][0])


### FIXED CODE ###

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

ans_li = [-1]*n
queue=[0]
visited = [False]*n

while queue:
    x = queue.pop(0)
    for g in map_li[x]:
        if visited[g]==False:
            queue.append(g)
            if ans_li[g]==-1:
                ans_li[g]=x
                visited[g]=True 
if -1 in ans_li[1:]:
    print('No')
else:
    print('Yes')
    for ans in ans_li[1:]:
        print(ans+1)
### BUGGY CODE ###

from sys import stdin

N = int(stdin.readline())
A = list(map(int,stdin.readline().split()))
Q = int(stdin.readline())
D = dict()
S = set()
sum=0

for y in A:
    sum+=y
    s = len(S)
    S.add(y)
    if len(S)==s:
        D[y]+=1
    else:
        D[y]=1



for u in range(0,Q):
    U= list(map(int,stdin.readline().split()))
    SS=S.copy()
    SS.add(U[0])
    if len(SS)==len(S):

        SS.add(U[1])
        if len(SS)==len(S):
            sum+=(D[U[0]])*(U[1]-U[0])

            D[U[1]]+=D[U[0]]
            D[U[0]]=0
        else:
            sum += (D[U[0]]) * (U[1] - U[0])
            D[U[1]]=D[U[0]]
            D[U[0]]=0
        S=SS

    print(sum)

### FIXED CODE ###

from sys import stdin

N = int(stdin.readline())
A = list(map(int,stdin.readline().split()))
A.sort()
Q = int(stdin.readline())
D = dict()
S = set(A)
sum=0
count=0

for y in range(0,N):
    sum+=A[y]
    if y>0 and A[y]!=A[y-1]:
        D[A[y-1]]=count
        count=1
    elif y==0:
        count=1
    else:
        count+=1
    if y==N-1:
        D[A[y]]=count

for u in range(0,Q):
    U= list(map(int,stdin.readline().split()))
    if U[0] in D:
        sum+=(D[U[0]])*(U[1]-U[0])
        if U[1] in D:
            D[U[1]]+=D[U[0]]
        else:
            D[U[1]]=D[U[0]]
        D[U[0]]=0


    print(sum)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().strip().split()))
k=1
f=0
for i in range(N):
	k=k*A[i]
	if k>10**18:
		f=1
	if A[i]==0:
		f=0
		break
if f==1:
	print(-1)
else:
	print(k)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().strip().split()))
k=1
f=0
if 0 in A:
	print(0)
else:
	for i in range(N):
		k=k*A[i]
		if k>10**18:
			f=1
			break
	if f==1:
		print(-1)
	else:
		print(k)
### BUGGY CODE ###

from math import log2,ceil
from collections import defaultdict
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
cnt=defaultdict(lambda :0)

for i in range(n):
    temp=a[i]
    if temp==0:continue
    digit=len(bin(temp))-2
    for j in range(ceil(digit)+1):
        if (temp>>j)&1:
            cnt[j]+=1

#print(cnt)
ans=0
for digit,count in cnt.items():
    ans=(ans+pow(2,digit)*count*(n-count))%mod
print(ans%mod)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
a=tuple(map(int,input().split()))
mod=10**9+7
cnt=[0]*60

for temp in a:
    if temp==0:continue
    digit=len(bin(temp))-2
    for j in range(digit):
        if (temp>>j)&1:
            cnt[j]=cnt[j]+1

#print(cnt)
ans=0
for i in range(60):
    if cnt[i]==0:continue
    ans=(ans+pow(2,i)*cnt[i]*(n-cnt[i]))%mod
print(ans%mod)
### BUGGY CODE ###

import heapq
n=int(input())
A=[int(i) for i in input().split()]
AL=A[:n]
ALS=[0]*(n+1)
ALS[0]=sum(AL)
heapq.heapify(AL)
for i in range(n):
  heapq.heappushpop(AL,A[n+i])
  ALS[i+1]+=sum(AL)
AR=[]
for i in range(2*n,3*n):
  AR.append(-A[i])
ARS=[0]*(n+1)
ARS[0]=-sum(AR)
heapq.heapify(AR)
for i in range(n):
  heapq.heappushpop(AR,-A[2*n-i-1])
  ARS[i+1]+=-sum(AR)
ARS=ARS[::-1]
ans=-float("inf")
for i in range(n+1):
  ans=max(ans,ALS[i]-ARS[i])
print(ans)

### FIXED CODE ###

import heapq
n=int(input())
A=[int(i) for i in input().split()]
AL=A[:n]
AR=[0]*n
for i in range(2*n,3*n):
  AR[i-2*n]-=A[i]
ALS,ARS=[0]*(n+1),[0]*(n+1)
ALS[0],ARS[0]=sum(AL),sum(AR)
heapq.heapify(AL)
heapq.heapify(AR)
for i in range(n):
  l,r=A[n+i],-A[2*n-i-1]
  heapq.heappush(AL,l)
  ALS[i+1]=ALS[i]+l-heapq.heappop(AL)
  heapq.heappush(AR,r)
  ARS[i+1]=ARS[i]+r-heapq.heappop(AR)
ans=-float("inf")
for i in range(n+1):
  ans=max(ans,ALS[i]+ARS[n-i])
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
wd = [tuple(map(int, input().split())) for i in range(N)]

d = 0
dp = [0]*N
l = 0
r = 10**27
while(r - l > 1):
    tmp = (l+r)//2
    num = 0
    for w, d in wd:
        if w <= tmp:
            num += ((tmp - w) // d) + 1
    if num >= K:
        r = tmp
    else:
        l = tmp

print(r)


### FIXED CODE ###

import sys
N, K = map(int, input().split())
input = sys.stdin.readline
wd = [tuple(map(int, input().split())) for i in range(N)]
wd.sort()
d = 0
dp = [0]*N
l = 0
r = wd[0][0] + wd[0][1]*K
while(r - l > 1):
    tmp = (l+r)//2
    num = 0
    for w, d in wd:
        if w <= tmp:
            num += ((tmp - w) // d) + 1
    if num >= K:
        r = tmp
    else:
        l = tmp

print(r)
### BUGGY CODE ###

h,w=map(int, input().split())
s=[[0 for _ in range(w)] for _ in range(h)]
for j in range(h):
    s[j]=list(input())
l=[[0 for _ in range(w)] for _ in range(h)]
r=[[0 for _ in range(w)] for _ in range(h)]
u=[[0 for _ in range(w)] for _ in range(h)]
d=[[0 for _ in range(w)] for _ in range(h)]
max=0

for i in range(h):
    for j in range(w):
        if s[i][j]=='#':
            l[i][j]=0
        else:
            if j==0:
                l[i][j]=1
            else:
                l[i][j]=l[i][j-1]+1
                
for j in range(w):
    for i in range(h):
        if s[i][j]=='#':
            u[i][j]=0
        else:
            if i==0:
                u[i][j]=1
            else:
                u[i][j]=u[i-1][j]+1
                      
for i in range(h):
    for j in range(w-1,-1,-1):
        if s[i][j]=='#':
            r[i][j]=0
        else:
            if j==w-1:
                r[i][j]=1
            else:
                r[i][j]=r[i][j+1]+1

for j in range(w):
    for i in range(h-1,-1,-1):
        if s[i][j]=='#':
            d[i][j]=0
        else:
            if i==h-1:
                d[i][j]=1
            else:
                d[i][j]=d[i+1][j]+1
                   
for i in range(h):
    for j in range(w):        
        total=l[i][j]+r[i][j]+d[i][j]+u[i][j]

        if max<total:
            max=total

print(max-3)

### FIXED CODE ###

h,w=map(int, input().split())
s=[[0 for _ in range(w)] for _ in range(h)]
for j in range(h):
    s[j]=list(input())
l=[[0 for _ in range(w)] for _ in range(h)]
r=[[0 for _ in range(w)] for _ in range(h)]
u=[[0 for _ in range(w)] for _ in range(h)]
d=[[0 for _ in range(w)] for _ in range(h)]
max=0

for i in range(h):
    for j in range(w):
        if s[i][j]=='#':
            l[i][j]=0
            u[i][j]=0
        else:
            if j==0:
                l[i][j]=1
            else:
                l[i][j]=l[i][j-1]+1
            if i==0:
                u[i][j]=1
            else:
                u[i][j]=u[i-1][j]+1
                      
for i in range(h-1,-1,-1):
    for j in range(w-1,-1,-1):
        if s[i][j]=='#':
            r[i][j]=0
            d[i][j]=0
        else:
            if j==w-1:
                r[i][j]=1
            else:
                r[i][j]=r[i][j+1]+1
            if i==h-1:
                d[i][j]=1
            else:
                d[i][j]=d[i+1][j]+1
                   
for i in range(h):
    for j in range(w):        
        total=l[i][j]+r[i][j]+d[i][j]+u[i][j]

        if max<total:
            max=total

print(max-3)
### BUGGY CODE ###

from sys import stdin,stdout
from sys import setrecursionlimit as SRL; SRL(10**7)
rd = stdin.readline
rrd = lambda: map(int, rd().strip().split())

n, q = rrd()

v = [[] for _i in range(n + 10)]

for i in range(n - 1):
    x, y = rrd()
    v[x].append(y)
    v[y].append(x)

add = [0] * (n + 10)

for i in range(q):
    p, x = rrd()
    add[p] += x


def dfs(now, fa):
    add[now] += add[fa]
    for i in v[now]:
        if i == fa:
            continue
        dfs(i, now)


dfs(1, 0)

stdout.write(" ".join(map(str,add[1:n+1])))


### FIXED CODE ###

from sys import setrecursionlimit as SRL, stdin, stdout

SRL(10 ** 7)
rd = stdin.readline
rrd = lambda: map(int, rd().strip().split())

n, q = rrd()

v = [[] for _i in range(n + 10)]

for i in range(n - 1):
    x, y = rrd()
    v[x].append(y)
    v[y].append(x)

add = [0] * (n + 10)

for i in range(q):
    p, x = rrd()
    add[p] += x

p = [(1, 0)]
vis = [0] * (n + 2)
while len(p):
    now, fa = p.pop()
    add[now] += add[fa]
    vis[now] = 1
    for i in v[now]:
        if not vis[i]:
            p.append((i,now))

stdout.write(" ".join(map(str, add[1:n + 1])))
### BUGGY CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

H, W, D = MAP()
grid = build_grid(H, W, 0, int)
HW = {}
for i in range(H):
    for j in range(W):
        HW[grid[i][j]-1] = (i, j)

# nxt[k][i] := iからスタートして、2^k回移動した後にいる位置
nxt = list2d(17, H*W, -1)
# cost[k][i] := iからスタートして、2^k回移動した時にかかるコスト
cost = list2d(17, H*W, INF)
for h in range(H):
    for w in range(W):
        cur = grid[h][w] - 1
        if cur + D < H * W:
            h2, w2 = HW[cur+D]
            # 1つ先の移動先とコストを記録
            nxt[0][cur] = cur + D
            cost[0][cur] = abs(h-h2) + abs(w-w2)

# ダブリングのテーブル構築
for k in range(1, 17):
    for i in range(H*W):
        if nxt[k-1][i] == -1:
            continue
        nxt[k][i] = nxt[k-1][nxt[k-1][i]]
        cost[k][i] = cost[k-1][i] + cost[k-1][nxt[k-1][i]]

for i in range(INT()):
    l, r = MAP()
    l -= 1; r -= 1
    cnt = (r - l) // D
    cur = l
    ans = 0
    # cnt回先に進む時のコストを確認
    for k in range(16, -1, -1):
        if cnt & 1<<k:
            ans += cost[k][cur]
            cur = nxt[k][cur]
    print(ans)


### FIXED CODE ###

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

import sys
input = sys.stdin.readline

H, W, D = map(int, input().split())
HW = []
for i in range(H):
    HW.append(list(map(int, input().split())))

# 各マス番号の座標位置をメモしておく
pos = [None] * (H*W+1)
for i in range(H):
    for j in range(W):
        pos[HW[i][j]] = (i, j)
# 間隔をDずつ空けた累積和
sm = [0] * (H*W+1)
for i in range(D+1, H*W+1):
    sm[i] = sm[i-D] + abs(pos[i][0] - pos[i-D][0]) + abs(pos[i][1] - pos[i-D][1])
# 各QはO(1)で解けるはず
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(sm[r] - sm[l])
### BUGGY CODE ###

# 初期入力
import numpy as np
import sys
input = sys.stdin.readline
A,B = (int(i) for i in input().split())
AB =np.array([i for i in range(A,B+1)])
digit_max=40

#
ans =""
for i in range(digit_max):
    c1 =np.count_nonzero(AB &1)
    c1 %= 2
    ans +=str(c1)
    AB >>=1
ans =ans[::-1]
ans =int(ans,2)
print(ans)

### FIXED CODE ###

def xor_sum(n):
    #0からの連続数のXOR和は４つ目が０（初項）
    st =n -n%4
    n_list =[i for i in range(st,n+1)]
    ans =0
    for i in n_list:
        ans ^=i
    return ans
# 初期入力

import sys
input = sys.stdin.readline
A,B = (int(i) for i in input().split())
ans =xor_sum(B) ^xor_sum(A-1)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3 ## -*- python -*-

s = input()
q = int(input())

for i in range(q):
    d = input()
    if d[0] == "1":
        s = s[::-1]
    else: # 2
        dd = d.split()
        f = int(dd[1])
        c = dd[2]
        if f == 1:
            s = c + s
        else: # f == 2
            s = s + c

print(s)

### FIXED CODE ###

#!/usr/bin/env python3 ## -*- python -*-
from collections import deque

def main():
    s = deque()
    s.extend(input())
    q = int(input())
    head = "l"
    for i in range(q):
        d = input()
        if d[0] == "1":
            if head == "l":
                head = "r"
            else:
                head = "l"
        else: # 2
            dd = d.split()
            f = int(dd[1])
            c = dd[2]
            if f == 1:
                if head == "l":
                    s.appendleft(c)
                else:
                    s.append(c)
            else: # f == 2
                if head == "l":
                    s.append(c)
                else:
                    s.appendleft(c)

    if head == "r":
        s.reverse()
    ans = ''.join(s)
    print(ans)
main()
### BUGGY CODE ###

N = int(input())
S = input()
d = {}
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            st = ''.join([S[i], S[j], S[k]])
            d[st] = True
print(len(d))


### FIXED CODE ###

N = int(input())
S = input()
d = {}
k1 = [0 for i in range(10)]
for i in range(N-2):
    if k1[int(S[i])] != 0: continue
    k1[int(S[i])] += 1
    k2 = [0 for i in range(10)]
    for j in range(i+1, N-1):
        if k2[int(S[j])] != 0: continue
        k2[int(S[j])] += 1
        for k in range(j+1, N):
            st = ''.join([S[i], S[j], S[k]])
            d[st] = True
print(len(d))
### BUGGY CODE ###

N = int(input())
A = []
for _ in range(N):
    a = int(input())
    A.append(a)
amax = max(A)
amaxcnt = A.count(amax)

B = []
for i in range(N):
    B = A[:]
    bi = B.pop(i)
    if bi == amax and amaxcnt == 1:
        B.sort()
        print(B.pop())
    else:
        print(amax)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]
amax = max(A)
amaxcnt = A.count(amax)

for i in range(N):
    ai = A[i]
    if ai == amax and amaxcnt == 1:
        A.pop(i)
        print(max(A))
        A.insert(i, 0)
    else:
        print(amax)
### BUGGY CODE ###

N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))

now = 1
path = [1]

for i in range(N + 2):
    now = A[now]
    i += 1
    if now in path: break
    path.append(now)

if i >= K:
    print(path[K])
    quit()

lo_start = path.index(now)
lo_len = i - lo_start
loop = path[lo_start:]

ans = loop[(K - lo_start) % lo_len]

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))

now = 1
path = [1]

for i in range(N + 2):
    now = A[now]
    path.append(now)

if i >= K:
    print(path[K])
    quit()

now = path.pop()
lo_start = i - 1
while path[lo_start] != now:
    lo_start -= 1

loop = path[lo_start:]

ans = loop[(K - path.index(now)) % len(loop)]

print(ans)
### BUGGY CODE ###

import collections as col
import numpy as np
import math as ma
import scipy.misc as spm #miscellaneous

MOD = 10**9 + 7
def inv(a): return pow(a, MOD-2, MOD)
def comb(n,r,MOD):
    ans = ma.factorial(n)%MOD * inv(ma.factorial(r)) * inv(ma.factorial(n-r))
    return ans%MOD

def prime(n):
    ans = []
    for i in range(2, int(n**0.5)+1):
        while not n%i: n //= i; ans.append(i)
    if n != 1: ans.append(n)
    return ans

n,m = map(int,input().split())
cnt = col.Counter(prime(m))

ans = 1
for key,val in cnt.items():
    #ans *= comb(val + n-1, n-1)
    ans *= comb(val + n-1, n-1, MOD)
    ans %= MOD
print(ans)



### FIXED CODE ###

import collections as col
import numpy as np
import math as ma
import scipy.misc as spm #miscellaneous

MOD = 10**9 + 7
def inv(a): return pow(a, MOD-2, MOD)
def comb(n,r):
    ans = ma.factorial(n)%MOD * inv(ma.factorial(r)) * inv(ma.factorial(n-r))
    return ans%MOD

def prime(n):
    ans = []
    for i in range(2, int(n**0.5)+1):
        while not n%i: n //= i; ans.append(i)
    if n != 1: ans.append(n)
    return ans

n,m = map(int,input().split())
cnt = col.Counter(prime(m))

ans = 1
for key,val in cnt.items():
    #ans *= comb(val + n-1, n-1)
    ans *= spm.comb(val + n-1, n-1, exact=1)
    ans %= MOD
print(ans)
### BUGGY CODE ###

import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

n=int(input())
if is_prime(n):
    print(len(str(n)))
    exit()

ns=int(math.sqrt(n)//1)

for i in range(ns,n+1):
    a=n/i
    if a%1==0:
        s=i
        break
s=str(s)
print(len(s))

### FIXED CODE ###

from math import sqrt
n=int(input())
sn=int(sqrt(n)//1)

for i in range(sn,0,-1):
    if n%i==0:
        s=n//i
        break
    
print(len(str(s)))
### BUGGY CODE ###

s=list(input())
p=0
for i in range(int(input())):
    a=list(map(str,input().split()))
    if len(a)==1:
        p+=1
    else:
        if p%2:
            if a[1]=="2":
                s.insert(0,a[2])
            else:
                s.append(a[2])
        else:
            if a[1]=="1":
                s.insert(0,a[2])
            else:
                s.append(a[2])
ans=""
if p%2==1:
    for i in s[::-1]:
        ans+=i
else:
    for i in s:
        ans+=i
print(ans)

### FIXED CODE ###

from collections import deque
s=deque(list(input()))
p=0
for i in range(int(input())):
    a=list(map(str,input().split()))
    if len(a)==1:
        p^=1
    else:
        if p%2:
            if a[1]=="2":
                s.appendleft(a[2])
            else:
                s.append(a[2])
        else:
            if a[1]=="1":
                s.appendleft(a[2])
            else:
                s.append(a[2])
ans=""
if p%2==1:
    while s:
        ans+=s.pop()
else:
    while s:
        ans+=s.popleft()
print(ans)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = [int(i) for i in input().split()] 
ls = np.array(a)

for ind in range(int(n/2), 0, -1):
    tmp = list(range(2*ind-1, n, ind))
    if a[ind-1] == ls[tmp].sum()%2:
        ls[ind-1] = 0
    else:
        ls[ind-1] = 1
        
print(sum(ls))
ans = np.where(ls==1)[0] + 1
ans = list(ans.astype(str))
print(' '.join(ans))

### FIXED CODE ###

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

st = int(n/2)
ans =  [i+st+1 for i, n in enumerate(a[st:]) if n ==1] 
for ind in range(st, 0, -1):
    tmp = [ls[i] for i in range(2*ind-1, n, ind)]
    s = sum(tmp)%2
    if a[ind-1] == s:
        ls[ind-1] = 0
    else:
        ls[ind-1] = 1
        ans.append(ind)
        
print(sum(ls))
print(' '.join(map(str, ans)))
### BUGGY CODE ###

def main():
    mod = 998244353
    s, k = input().split()
    k, n, one, cnt, z, zero_list = int(k), len(s), s.count("1")+1, 0, 0, []
    for i in range(n):
        if s[i] == "0":
            zero_list.append(cnt)
            cnt = 0
        else:
            cnt += 1
    mm = min(one-1, k)

    dp = [[0]*(mm+1) for _ in [0]*one]
    dp[0][0] = 1

    for i in zero_list:
        dp2 = [[0]*(mm+1) for _ in [0]*one]
        for jl in range(z+i, one):
            for x in range(i, min(one, jl+1, mm+i+1)):
                dp2[jl][x-i] = (dp2[jl][x-i]+sum([dp[jl-x+p][p]
                                                  for p in range(min(one, x-i+1))])) % mod
            for p in range(min(one, mm+1)):
                dp2[jl][p] = (dp2[jl][p]+sum([dp[jl-l][p]
                                              for l in range(min(one, i, jl-p+1))])) % mod
        z += i
        dp = dp2
    print(sum([sum(i) for i in dp]) % mod)


main()


### FIXED CODE ###

def main():
    mod = 998244353
    s, k = input().split()
    k = int(k)
    n = len(s)

    one = s.count("1")

    cnt = 0
    zero_list = []
    for i in range(n):
        if s[i] == "0":
            zero_list.append(cnt)
            cnt = 0
        else:
            cnt += 1

    z = 0
    mm = min(one, k)

    dp = [[0]*(one+1) for _ in [0]*(one+1)]
    dp[0][0] = 1

    for i in range(len(zero_list)):
        dp2 = [[0]*(mm+1) for _ in [0]*(one+1)]
        base = zero_list[i]
        # j:何個今までに入れたか
        for j in range(one+1):
            # l:何個入れるか
            for l in range(one+1-j):
                if l < z+base-j:
                    continue
                ml = max(l-base, 0)
                # p:これまでのペナルティ
                for p in range(min(one, k)+1):
                    q = p+ml
                    if q <= mm:
                        dp2[j+l][q] = (dp2[j+l][q]+dp[j][p]) % mod
                    else:
                        break
        z += base
        dp = dp2
    print(sum([sum(i) for i in dp]) % mod)


main()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split())) 
A.sort()
ans = [0] * (10**6+1)
watched = set()
for i in A:
    ans[i] = 1
for i in range(N-1):
    if A[i] == A[i+1]:
        ans[A[i]] = 0
    temp = A[i]
    if temp in watched:
        continue       
    for j in range(i+1, N):
        if A[j]%temp == 0:
            ans[A[j]] = 0
            watched.add(A[j])
print(sum(ans))

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split())) 
ans = set(A)
for k, v in Counter(A).items():
    if v != 1:
        ans.discard(k)
    temp = {k*i for i in range(2,10**6//k + 1)}
    ans -= ans&temp
print(len(ans))
### BUGGY CODE ###

import math
N, K = map(int, input().split())
A = [int(a) for a in input().split()]

A.sort()
from operator import mul
from functools import reduce

def comb(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

maxi = 0
for i in range(K-1,N):
    maxi += A[i]*comb(i,K-1)

mini = 0
A.sort(reverse=True)
for j in range(K-1,N):
    mini += A[j]*comb(j,K-1)

print((maxi-mini)%(10**9 + 7))


### FIXED CODE ###

import math
N, K = map(int, input().split())
A = [int(a) for a in input().split()]

A.sort()

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
Ne = 10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, Ne + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )



maxi = 0
for i in range(K-1,N):
    maxi += A[i]*cmb(i, K-1, mod)

mini = 0
A.sort(reverse=True)
for j in range(K-1,N):
    mini += A[j]*cmb(j, K-1, mod)

print((maxi-mini)%mod)
### BUGGY CODE ###

from sys import stdin
n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
def knapsack(n,w,li):
    #li[i][0]が重さ,li[i][1]が価値
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(li[i][0]-1,w+1):
            if total_w - li[i][0] >= 0:
                dp[i+1][total_w] = max(dp[i][total_w],dp[i][total_w-li[i][0]]+li[i][1])
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return dp[-1][-1]
print(knapsack(n,w,li))

### FIXED CODE ###

from sys import stdin
n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
def knapsack(n,w,li):
    #li[i][0]が重さ,li[i][1]が価値
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(w+1):
            if total_w - li[i][0] >= 0:
                dp[i+1][total_w] = max(dp[i][total_w],dp[i][total_w-li[i][0]]+li[i][1])
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return max(dp[-1])
print(knapsack(n,w,li))