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

import queue
inf = 10**18
n = int(input())
a = list(map(int,input().split()))
way = [[] for i in range(n)]
for i in range(n-1):
    u,v = map(int,input().split())
    u,v = u-1,v-1
    way[u].append(v)
    way[v].append(u)

def Mnsr(ni,mns):
    mnsi = mns + [inf]
    l = 0
    r = len(mns)
    while l < r:
        mid = (r-l)//2+l
        if ni < mnsi[mid]:
            r = mid
        else:
            l = mid+1

    if not mnsi[l-1] == ni:
        mnsi[l] = ni
    return mnsi

def ansfind(arr):
    l = 0
    r = len(arr)-1
    while l < r:
        mid = l + (r-l)//2
        if arr[mid] == inf:
            r = mid
        else:
            l = mid+1
    return l-1


ans = [1 for i in range(n)]
q = queue.Queue()
for i in way[0]:
    q.put((i,0,Mnsr(a[i],[0,a[0],inf])))

while not q.empty():
    i,pi,mns = q.get()
    ans[i] = ansfind(mns)
    for j in way[i]:
        if pi == j:
            continue
        q.put((j,i,Mnsr(a[j],mns)))

for i in ans:
    print(i)


### FIXED CODE ###

'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)



def main():
    n = int(ipt())
#    n = 2*10**5
    a = [int(i) for i in ipt().split()]
#    a = [i+1 for i in range(n)]
    way = [[] for i in range(n)]
    for i in range(n-1):
        u,v = map(int,ipt().split())
        u -= 1;v -= 1
        way[u].append(v)
        way[v].append(u)
#    way = [[i-1,i+1] for i in range(n)]
#    way[0] = [1]
#    way[n-1] = [n-2]
    ans = [0]*n
    dp = [10**18]*n
    stk = []

    def solve(ni,pi):
        ai = a[ni]
        pt = bisect.bisect_left(dp,ai)
        stk.append((pt,dp[pt]))
        dp[pt] = ai
        ans[ni] = bisect.bisect_left(dp,10**18-1)
        for i in way[ni]:
            if i == pi:
                continue
            else:
                solve(i,ni)
        pl,val = stk.pop()
        dp[pl] = val
        return None

    solve(0,-1)

    for i in ans:
        print(i)

    return None

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

import numpy as np
N,K,Q = map(int,input().split())
point = np.array([K] * N)
minus = np.array([-1] * N)
for i in range(0,Q):
    A = int(input())
    point += minus
    point[A-1] += 1
for i in range(0,N):
    if point[i] > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N,K,Q = map(int,input().split())
point = [0 for i in range(0,N)]
for i in range(0,Q):
    A = int(input())
    point[A-1] += 1
for i in range(0,N):
    if Q - point[i] < K:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

s = input() #sys.stdin.readlineは最後が改行
n =len(s)

from collections import defaultdict
amari = defaultdict(lambda:0)
amari[0]=1
num=0
tmp=0
ans =0

for i in range(n):
    num = tmp + int(s[-1-i])*((10**i)%2019)
    tmp = num%2019
    amari[tmp]+=1

    if amari[tmp]>1:
        val = amari[tmp]
        ans -= (val-1)*(val-2)//2
        ans += (val)*(val-1)//2

print(ans)


### FIXED CODE ###

s = input() #sys.stdin.readlineは最後が改行
n =len(s)

from collections import defaultdict
amari = defaultdict(lambda:0)
amari[0]=1
num=0
tmp=0
ans =0

for i in range(n):
    num = tmp + int(s[-1-i])*pow(10,i,2019)
    tmp = num%2019
    amari[tmp]+=1

    if amari[tmp]>1:
        val = amari[tmp]
        ans -= (val-1)*(val-2)//2
        ans += (val)*(val-1)//2

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

N,P = map(int, input().split())
S = list(map(int,input()))

if P == 2 or P==5:
    # 左端が2,5となる文字列を見つけてくる
    ans=0
    for i,s in enumerate(S):
        if s%P==0:
            ans+=i+1
    print(ans)
else:
    # mod P の和を足していく
    ans = 0
    from collections import deque
    U=deque()
    U_sum=deque()
    ten = 1
    for i,s in enumerate(S[::-1]):
        new = (s*ten) % P
        U.appendleft(s*10**i % P)
        ten *= 10
        ten %= P
    same_p = [0 for _ in range(P)]
    for i in range(len(U)):
        u = U[-i-1]
        if i == 0:
            U_sum.appendleft(u)
            same_p[u]+=1
            continue
        new = (U_sum[-i]+u) % P
        U_sum.appendleft(new)
        same_p[new] += 1

    for i,p in enumerate(same_p):
        if i == 0:
            # 自分だけでも選択できるから
            ans += p
        ans += int(p*(p-1) / 2)
    print(ans)

















### FIXED CODE ###

import sys
"""
方針：まず左端を固定して実際にPで割ったあまりを計算しながら数値列を伸ばしていけばO(N^2)で計算ができる
文字列の左右を固定した場合に（部分文字列について？）Pで割ったあまりを計算できないか，定式化を考えてみよう．
Ui := S[i:N]をSのi文字以降を評価した整数と置く．便宜上UN+1=0とする．
この時Sのi文字目からj文字目までを評価した整数は(Ui - Uj+1)/10^(j+1-i)と表せる．

"""

sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
read = sys.stdin.read

n, p = [int(i) for i in readline().split()]
s = input()

if p == 2 or p == 5:
    ans = 0
    for i, c in enumerate(s):
        if int(c) % p == 0:
            ans += i + 1
    print(ans)
    exit()

res = [0] * p
res[0] = 1
t = 1
now = 0
for i in s[::-1]:
    i = int(i)
    now += i * t
    now %= p
    res[now] += 1
    t = t * 10 % p

ans = 0
for i in res:
    ans += i * (i - 1) // 2

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

# /usr/bin/python
# -*- coding: utf-8 -*-
import sys


n,k = map(int, sys.stdin.readline().rstrip().split())
hn = list(map(int, sys.stdin.readline().rstrip().split()))
dp = [-1] * n

dp[0] = 0
for i in range(1,n):
  ret = sys.maxsize
  for j in range(1,min(k+1,i+1)):
    ret = min(ret, dp[i-j]+abs(hn[i-j]-hn[i]))
  dp[i] = ret
print(dp[n-1])



### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
import sys
import numpy as np

n,k = map(int, sys.stdin.readline().rstrip().split())
h = np.array(list(map(int, sys.stdin.readline().rstrip().split())))

dp = np.zeros(n, dtype=np.int)

for i in range(1,n):
  if i < k:
    dp[i] = np.min(dp[:i] + np.abs(h[i]-h[:i]))
  else:
    dp[i] = np.min(dp[i-k:i] + np.abs(h[i]-h[i-k:i]))

print(dp[n-1])
### BUGGY CODE ###

N = int(input())
flag = 0
for a in range(1,3501):
    if flag == 1:
        break
    for b in range(1,3501):
        M = (4*a*b - N*a - N*b)
        C = N*a*b
        if M < 0 :
            continue
        elif M != 0:
            if C//M == C/M:
                c = C//M
                print(a,b,c)
                flag = 1
                break

### FIXED CODE ###

import sys
N = int(input())
for h in range(1,3501):
    for n in range(1,3501):
        if 4*n*h > N*n + N*h and (N*n*h) % (4*n*h-N*h-N*n) == 0:
            w =  (N*n*h) // (4*n*h-N*h-N*n)
            print(n,h,w)
            sys.exit()
### BUGGY CODE ###

n = int(input())
la = list(map(int, input().split()))
ans = 0
for i in range(n-1):
  ans = (ans%(10**9+7) + la[i+1]*sum(la[:i+1])%(10**9+7))%(10**9+7)
print(ans)

### FIXED CODE ###

n = int(input())
la = list(map(int, input().split()))
MOD = (10**9+7)
ans = 0
nn = 0
for i in range(n):
  ans %= MOD
  ans += la[i]%MOD
  nn %= MOD
  nn += (la[i]**2)%MOD
ans = (ans**2-nn+10**9+7)*pow(2, -1, MOD)%MOD
print(ans)
### BUGGY CODE ###

k,s=map(int,input().split())
cnt=0
for i in range(k+1):
    for j in range(k+1):
        for k in range(k+1):
            sum=i+j+k
            if sum==s:
                cnt+=1
print(cnt)

### FIXED CODE ###

k,s=map(int,input().split())
cnt=0
for x in range(k+1):
    for y in range(k+1):
        z=s-x-y
        if 0<=z and z<=k:
          cnt+=1
print(cnt)
### BUGGY CODE ###

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

a = 1
b = 1

while P >= a**N:
	if P % a**N == 0:
		b = a
	a += 1

print(b)


### FIXED CODE ###

N, P = map(int, input().split())
import math

a = 2
b = 1

if N == 1 :
	print(P)
else:
	while math.log(P) >= N * math.log(a):
		if P % a**N == 0:
			P /= a**N
			b *= a
			a = 1
		a += 1
	print(b)
### BUGGY CODE ###

k, s = list(map(int, input().split()))
xyz_l = []
r_k = range(k+1)[::-1]

for x in r_k:
    a = s-x
    if a > k*2:
        break
    for y in r_k:
        b = a - y
        if b > k:
            break
        for z in r_k:
            c = b - z
            if c == 0:
                xyz_l.append([x, y, z])
print(len(xyz_l))


### FIXED CODE ###

k, s = list(map(int, input().split()))
count = int(0)

for x in range(k+1)[::-1]:
    yz = s - x
    if yz > k*2:
        break
    for y in range(k+1)[::-1]:
        z = yz - y
        if x >= y >= z >= 0:
            if len({x, y, z}) == 1:
                count += 1
            elif len({x, y, z}) == 2:
                count += 3
            else:
                count += 6

print(count)
### BUGGY CODE ###

h,w,m=map(int,input().split())
g=[0]*h
l=[0]*w
b=[]
for i in range(m):
  x,y=map(int,input().split())
  g[x-1]+=1
  l[y-1]+=1
  b.append((x-1,y-1))
mxg=max(g);mxl=max(l)
mg=[i for i,x in enumerate(g) if x==mxg]
ml=[i for i,x in enumerate(l) if x==mxl]
c=0
for x,y in b:
  if x in mg and y in ml:
    c+=1
print(mxg+mxl-(c==(len(mg)*len(ml))))

### FIXED CODE ###

h,w,m=map(int,input().split())
g=[0]*h
l=[0]*w
b=[]
for i in range(m):
  x,y=map(int,input().split())
  g[x-1]+=1
  l[y-1]+=1
  b.append((x-1,y-1))
mxg=max(g);mxl=max(l)
mg=set([i for i,x in enumerate(g) if x==mxg])
ml=set([i for i,x in enumerate(l) if x==mxl])
c=0
for x,y in b:
  if x in mg and y in ml:
    c+=1
print(mxg+mxl-(c==(len(mg)*len(ml))))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(M):
    b, c = map(int, input().split())
    A.extend([c] * b)
A.sort(reverse = True)
ans = 0
for i in range(N):
    ans += A[i]
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
table = []
for i in range(N):
    table.append((A[i], 1))
for i in range(M):
    b, c = map(int, input().split())
    table.append((c, b))

table = sorted(table)
cnt = N
ans = 0
while cnt > 0:
    #print(ans,s)
    c, b = table.pop()
    if b >= cnt:
        ans += c*cnt
        break
    ans += c*b
    cnt -= b
print(ans)
### BUGGY CODE ###

import sys
import itertools as it
input = sys.stdin.readline

N, M, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

AS = list(it.accumulate(A))
BS = list(it.accumulate(B))
AS.insert(0,0)
BS.insert(0,0)
max = 0
for i in range(len(AS)):
    a = AS[i]
    if a > K:
        continue
    for j in range(len(BS)):
        b = BS[j]
        if a + b > K:
            break
        if max < i + j:
            max = i + j

print(max)

### FIXED CODE ###

import sys
import itertools as it
input = sys.stdin.readline

N, M, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

AS = list(it.accumulate(A))
BS = list(it.accumulate(B))
AS.insert(0,0)
BS.insert(0,0)
max = 0
for i in range(N+1):
    a = AS[i]
    if a > K:
        continue
    if max - i > 0:
        j = max - i
    else:
        j = 0
    while j < M + 1:
        b = BS[j]
        if a + b > K:
            break
        if max < i + j:
            max = i + j
        j += 1

print(max)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
   s.append(input().rstrip('\n'))

INF = 10 ** 10
d = [INF] * (h*w)

stack = deque([[ch-1, cw-1, 0]])
stack_append = stack.append
stack_popleft = stack.popleft

nex = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i, j) in [(-1,0),(1,0),(0,-1),(0,1),(0,0)]:
            continue
        else:
            nex.append((i,j))

d[(ch-1) * w + (cw-1)] = 0
while stack:
    curh, curw, cnt = stack_popleft()
    if d[curh * w + curw] < cnt: continue
    #print(curh, curw, cnt)
    d[curh * w + curw] = cnt
    for dh, dw in ((-1,0), (1,0), (0,1), (0,-1)):
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            d[nh * w + nw] = cnt
            stack_append([nh, nw, cnt])
    for dh, dw in nex:
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            d[nh * w + nw] = cnt + 1
            stack_append([nh, nw, cnt+1])

# for item in d:
#     print(item)
gh -= 1
gw -= 1

if d[gh*w + gw] == INF:
    print(-1)
else:
    print(d[gh*w + gw])


### FIXED CODE ###

import heapq
class Dijkstra:
    INF = 10**18
    threshold = 10**9

    def __init__(self, N):
        self.MAX_V = N + 1
        self.dist = [self.INF] * self.MAX_V
        self.G = [[] for _ in range(self.MAX_V)]

    def insert(self, X, Y, cost): self.G[X].append(cost * self.threshold + Y)

    def dijkstra(self, st):
        q = []
        heapq.heappush(q, st)
        self.dist[st] = 0

        while len(q):
            p = heapq.heappop(q)
            cost = p // self.threshold
            node = p - cost * self.threshold
            if cost > self.dist[node]: continue
            for to in self.G[node]:
                to_cost = to // self.threshold
                to_node = to - to_cost * self.threshold
                to_cost += self.dist[node]
                if self.dist[to_node] > to_cost:
                    self.dist[to_node] = to_cost
                    heapq.heappush(q, to_cost * self.threshold + to_node)

h, w = map(int, input().split())
sh, sw = map(int, input().split())
eh, ew = map(int, input().split())

sh -= 1
sw -= 1
eh -= 1
ew -= 1

S = [input() for _ in range(h)]

di = Dijkstra(h*w)
for x in range(h):
    for y in range(w):
        if S[x][y] == '#': continue
        for i in range(-2, 3):
            for j in range(-2, 3):
                X = x + i
                Y = y + j
                if X < 0 or Y < 0 or X >= h or Y >= w or S[X][Y] == '#': continue
                D = abs(i) + abs(j)

                if D == 1: di.insert(x * w + y, X * w + Y, 0)
                if D >= 2: di.insert(x * w + y, X * w + Y, 1)

di.dijkstra(sh * w + sw)
ans = di.dist[eh * w + ew]
if ans == 10**18: print(-1)
else: print(ans)
### BUGGY CODE ###

from collections import defaultdict
n,W=list(map(int,input().split()))
li=[]
wr=[0]*n
vr=[0]*n
dd=defaultdict(lambda:0)
for i in range(n):
	w,v=map(int,input().split())
	wr[i]=w
	vr[i]=v
def maxv(i,w):
	if dd[(i,w)]!=0:
		return dd[(i,w)]
	if i==n:
		return 0
	if w+wr[i]>W:
		m=maxv(i+1,w)
		dd[(i,w)]=m
		return m
	a=vr[i]+maxv(i+1,w+wr[i])
	b=maxv(i+1,w)
	c=max(a,b)
	dd[(i,w)]=c
	return c
print(maxv(0,0))



### FIXED CODE ###

n,W=map(int,input().split())
dp=[0]*(W+1)
dd=dp.copy()
for i in range(n):
	w,v=map(int,input().split())
	for j in range(W):
		cw=j+w
		cv=dp[j]+v
		if cw <=W and dd[cw]<cv:
			dd[cw]=cv
	dp=dd.copy()
print(dp[W])
### BUGGY CODE ###

w, h, n = map(int, input().split())

vec = []
for i in range(n):
    x, y, x1, y1 = map(int, input().split())
    vec.append([x, y, i])
    vec.append([x1, y1, i])

sorted_node = []

vec.sort(key=lambda x: x[1])
for p in vec:
    if p[0] == 0:
        p[0] = -1
        p[1] = -1
        sorted_node.append(p)

vec.sort(key=lambda x: x[0])
for p in vec:
    if p[1] == h:
        p[0] = -1
        p[1] = -1
        sorted_node.append(p)

vec.sort(key=lambda x: x[1], reverse=True)
for p in vec:
    if p[0] == w:
        p[0] = -1
        p[1] = -1
        sorted_node.append(p)

vec.sort(key=lambda x: x[0], reverse=True)
for p in vec:
    if p[1] == 0:
        p[0] = -1
        p[1] = -1
        sorted_node.append(p)

colors = list(map(lambda x: x[2], sorted_node))

colors = list(filter(lambda x:colors.count(x) % 2 == 0, set(colors)))

stack = []

for node in sorted_node:
    if node[2] in colors:
        if not stack or stack[-1] != node[2]:
            stack.append(node[2])
        else:
            stack.pop()

print("NO" if stack else "YES")



### FIXED CODE ###

w, h, n = map(int, input().split())

vec = []

l = []
b = []
r = []
t = []
for i in range(n):
    x, y, x1, y1 = map(int, input().split())
    c = [x, y, x1, y1]
    if( ((c[0] == 0 or c[0] == w) or (c[1] == 0 or c[1] == h)) and ((c[2] == 0 or c[2] == w) or (c[3] == 0 or c[3] == h)) ):
        if x == 0:
            l.append([x, y, i])
        elif y == 0:
            t.append([x, y, i])
        elif x == w:
            r.append([x, y, i])
        elif y == h:
            b.append([x, y, i])
        if x1 == 0:
            l.append([x1, y1, i])
        elif y1 == 0:
            t.append([x1, y1, i])
        elif x1 == w:
            r.append([x1, y1, i])
        elif y1 == h:
            b.append([x1, y1, i])

sorted_node = (
          sorted(l, key=lambda x: x[1])
        + sorted(b, key=lambda x: x[0])
        + sorted(r, key=lambda x: x[1], reverse=True)
        + sorted(t, key=lambda x: x[0], reverse=True)
        )


stack = []

for node in sorted_node:
    if not stack or stack[-1] != node[2]:
        stack.append(node[2])
    else:
        stack.pop()

print("NO" if stack else "YES")
### BUGGY CODE ###

import numpy as np

n = int(input())

a = np.array([i for i in list(map(int, input().split()))])
d = {}
s = {}

for i in set(a):
  d[i] = len(a[a==i])
  
sum = 0
for k in d.values():
  if k>1:
    sum += (k*(k-1))//2

for i in range(n):
  nd = d[a[i]]
  ans = sum-(nd*(nd-1))//2
  nd -= 1
  if nd>1:
    ans += (nd*(nd-1))//2
  print(ans)

### FIXED CODE ###

import numpy as np

n = int(input())

a = np.array(list(map(int, input().split())))
d = [0] * (n+1)
s = {}

for i in a:
  d[i] += 1
  
sum = 0
for k in d:
  if k>1:
    sum += (k*(k-1))//2

for i in range(n):
  ans=sum-d[a[i]]+1
  print(ans)
### BUGGY CODE ###

h, n = map(int, input().split())
dp = [10**10]*(h+1)
dp[0] = 0
for _ in range(n):
    a, b = map(int, input().split())
    for start in range(h):
        if dp[start]==10**10:
            continue
        end = min(start+a, h)
        dp[end] = min(dp[end], dp[start]+b)
print(dp[h])


### FIXED CODE ###

h, n = map(int, input().split())
dp = [10**10]*(h+1)
dp[0] = 0
ab = []
for _ in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))

for a, b in ab:
    for start in range(h):
        end = min(start+a, h)
        dp[end] = min(dp[end], dp[start]+b)
print(dp[h])
### BUGGY CODE ###

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

cum_s = [[0 for _ in range(w+1)] for _ in range(h)]
for i in range(1, w+1):
    for j in range (h):
        cum_s[j][i] += (s[j][i-1] == '1') + cum_s[j][i-1]
#print(cum_s)

ans = 10 ** 6
for i in range(2 ** (h-1)):
    sep = []
    tmp = [0]
    for j in range(h-1):
        if (i >> j) & 1:
            tmp.append(j+1)
        else:
            if tmp != []:
                sep.append(tmp)
            tmp = [j+1]
    sep.append(tmp)
    #print(sep)
    
    idx = 0
    cnt = 0
    for j in range(1,w+1):
        flg = False
        for l in sep:
            tmp_sum = sum([cum_s[x][j] - cum_s[x][idx] for x in l])
            if tmp_sum > k:
                if j - idx == 1:
                    cnt = 10 ** 6
                flg = True
        
        if flg:
            cnt += 1
            idx = j-1 
    #print(len(sep)-1, cnt)
    ans = min(ans, len(sep)-1 + cnt)

if w == 1:
    x = sum([s[i] == '1' for i in range(h)])
    print(max(0, -(-x // k)-1))
elif h == 1:
    x = sum([s[0][i] == '1' for i in range(w)])
    print(max(0, -(-x // k)-1))
else:
    print(ans)

### FIXED CODE ###

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

cum_s = [[0 for _ in range(w+1)] for _ in range(h)]
for i in range(1, w+1):
    for j in range (h):
        cum_s[j][i] += (s[j][i-1] == '1') + cum_s[j][i-1]
#print(cum_s)

ans = 10 ** 6
for i in range(2 ** (h-1)):
    sep = []
    tmp = [0]
    for j in range(h-1):
        if (i >> j) & 1:
            tmp.append(j+1)
        else:
            if tmp != []:
                sep.append(tmp)
            tmp = [j+1]
    sep.append(tmp)
    #print(sep)
    
    idx = 0
    cnt = 0
    for j in range(1,w+1):
        flg = False
        for l in sep:
            tmp_sum = sum([cum_s[x][j] - cum_s[x][idx] for x in l])
            if tmp_sum > k:
                if j - idx == 1:
                    cnt = 10 ** 6
                flg = True
        
        if flg:
            cnt += 1
            idx = j-1 
    #print(len(sep)-1, cnt)
    ans = min(ans, len(sep)-1 + cnt)

if w == 1:
    x = sum([s[i] == '1' for i in range(h)])
    print(max(0, -(-x // k)-1))
elif h == 1:
    x = sum([s[0][i] == '1' for i in range(w)])
    print(max(0, -(-x // k)-1))
else:
    print(ans)
### BUGGY CODE ###

def zeros(h,*w): return [[0] * w[0]  for _ in range(h)] if w else [[0] * h  for _ in range(h)]

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

dp = zeros(n+1,W+1)

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

ans = max( dp[n] )

print(ans)

### FIXED CODE ###

def zeros(h,*w): return [[0] * w[0]  for _ in range(h)] if w else [[0] * h  for _ in range(h)]

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

dp = zeros(n+1,W+1)

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

ans = max( dp[n] )

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

import math
n=int(input())
ans=0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            ans+=math.gcd(math.gcd(i,j),k)
print(ans)

### FIXED CODE ###

import math
n=int(input())
ans=0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            ans+=math.gcd(math.gcd(i,j),k)
print(ans)
### BUGGY CODE ###

#ALDS1_3-C Elementary data structures - Doubly Linked List
n=int(input())
L=[]
for i in range(n):
    cmd=input().split()
    if(cmd[0]=="insert"):
        L=[cmd[1]]+L
    elif(cmd[0]=="delete" and cmd[1] in L):
        L.remove(cmd[1])
    elif(cmd[0]=="deleteFirst"):
        L.pop(0)
    if(cmd[0]=="deleteLast"):
        L.pop()
s=""
for i in L:
    s+=i+" "
print(s[:-1])

### FIXED CODE ###

#ALDS1_3-C Elementary data structures - Doubly Linked List
import collections
import sys
q = collections.deque()
n=int(input())
_input = sys.stdin.readlines()
cmds={"insert":lambda cmd: q.appendleft(cmd[1]),
      "delete":lambda cmd: q.remove(cmd[1]) if (q.count(cmd[1]) > 0) else "none",
      "deleteFirst":lambda cmd: q.popleft(),
      "deleteLast": lambda cmd: q.pop()
     }

for i in range(n):
    cmd=_input[i].split()
    cmds[cmd[0]](cmd)
print(*q)