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

# abc170_d.py
N = int(input())
A = list(map(int,input().split()))
cnt = 0
for i in range(N):
    can_devide = False
    for j in range(N):
        if A[i] % A[j] == 0 and i != j:
            # print(A[i] , A[j])
            can_devide = True
            break
    if not can_devide:
        cnt += 1
print(cnt)


### FIXED CODE ###

# abc170_d.py
N = int(input())
A = list(map(int,input().split()))
A.sort()
cnt = [0]*(10**6+1)
for i in A:
    if cnt[i]<1:
        multiple = 2
        while i*multiple <= 10**6:
            cnt[multiple*i]+=1
            multiple+=1
    cnt[i]+=1
ans = 0
for i in A:
    if cnt[i]==1:
        ans+=1
print(ans)
### BUGGY CODE ###

from math import sqrt

s = int(input())
n=int(sqrt(s))
x1=0
y1=0
y2=0
x3=0
for i in range(n):
    if s%(n-i)==0:
        x2=s//(n-i)
        y3=n-i
        break
    if s%(i+1)==0:
        x2=s//(i+1)
        y3=i+1
print(x1,y1,x2,y2,x3,y3)


### FIXED CODE ###

n = int(input())
N = 10**9
x1=0
y1=0
x2=N
y2=1
x3=N-n%N
y3=n//N+1
if n==10**18:
    x3=0
    y3=n//N

print(x1,y1,x2,y2,x3,y3)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

def dfs(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  while stack:
    v = stack[-1]
    marker = 0
    for u in edge[v]:
      if u==parent[v]:
        continue
      if parent[u]==N: #子へ降ろす
        marker = 1
        parent[u]=v
        stack.append(u)
      else: #子から吸い上げる
        ans[v] *= ans[u]+1
    if marker==0:
      stack.pop()
  return ans

def dfs2(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  while stack:
    v = stack.pop()
    for u in edge[v]:
      if u==parent[v]:
        continue
      parent[u]=v
      ans[u] *= (ans[v] // (ans[u]+1))+1
      stack.append(u)
    ans[v] %= M
  return ans

ans = [1]*N
dfs(0)
dfs2(0)
print(*ans, sep='\n')

### FIXED CODE ###

import sys,os,io
input = sys.stdin.readline
# input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = list(map(int, input().split()))
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

def dfs(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  while stack:
    v = stack[-1]
    marker = 0
    for u in edge[v]:
      if u==parent[v]:
        continue
      if parent[u]==N: #子へ降ろす
        marker = 1
        parent[u]=v
        stack.append(u)
      else: #子から吸い上げる
        ans[v] *= ans[u]+1
        ans[v] %=M
    if marker==0:
      stack.pop()
  return

def dfs2(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  p_value = [0]*N
  while stack:
    v = stack.pop()
    cum1 = [1]*(len(edge[v])+1)
    cum2 = [1]*(len(edge[v])+1)
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        cum1[i+1] = cum1[i]*(p_value[v]+1)%M
      else:
        cum1[i+1] = cum1[i]*(ans[u]+1)%M
    for i,u in enumerate(edge[v][::-1]):
      if u==parent[v]:
        cum2[-i-2] = cum2[-i-1]*(p_value[v]+1)%M
      else:
        cum2[-i-2] = cum2[-i-1]*(ans[u]+1)%M
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        continue
      parent[u]=v
      p_value[u] = cum1[i]*cum2[i+1]%M
      ans[u] *= (p_value[u]+1)
      ans[u] %= M
      stack.append(u)
    ans[v] %= M
  return

ans = [1]*N
dfs(0)
dfs2(0)
print(*ans, sep='\n')
### BUGGY CODE ###

n = int(input())
X = input()
pc = X.count('1')
nx = int(X, 2)

dp = [-1] * ((2*10**5)+1)
dp[0] = 0
dp[1] = 1

pcs = [0] * 2**16
for index in range(len(pcs)):
    pcs[index] = (index & 1) + pcs[index >> 1]
def popcnt(v):
    return (pcs[ v        & 0xffff] +
            pcs[(v >> 16) & 0xffff] +
            pcs[(v >> 32) & 0xffff] +
            pcs[(v >> 48)         ])

def f(n):
    if dp[n] >= 0:
        return dp[n]
    nn = n%popcnt(n)
    d = f(nn)+1
    dp[n] = d
    return d

tmp = pow(2, n)
for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまり2**iを引く
    tmp //= 2
    if (nx>>i)&1:
        if nx-tmp == 0:
            print(0)
            continue
        r = (nx-tmp)%(pc-1)
    else:
        r = (nx+tmp)%(pc+1)

    if r > 0:
        print(f(r) + 1)
    else:
        print(1)


### FIXED CODE ###

n = int(input())
X = input()
pc = X.count('1')
nx = int(X, 2)

def f(n):
    c = 0
    while n > 0:
        n %= bin(n).count('1')
        c += 1
    return c

nxp = nx%(pc+1)
nxm = nx%(pc-1) if pc > 1 else 0
for i in range(n-1, -1, -1):
    if (nx>>i)&1:
        # 2**iを引く
        if pc-1 == 0:
            print(0)
            continue
        p = pow(2, i, pc-1)
        r = (nxm-p)%(pc-1)
    else:
        # 2**iを足す
        r = (nxp+pow(2, i, pc+1))%(pc+1)

    print(f(r) + 1)
### BUGGY CODE ###

def solve():
  h,w = (int(i) for i in input().split())
  maze = [input() for _ in range(h)]
  visit = [[False]*w for i in range(h)]
  count = 0
  ans = 0
  
  white = []
  for i in range(h):
    for j in range(w):
      if maze[i][j] == ".":
        white.append((i,j))
      
  d = [(1,0),(0,1),(-1,0),(0,-1)]
  while white:
   x,y = white.pop(0)
   query = [(x,y,0)]
   while query:
    x,y,move = query.pop(0)
    nm = move + 1
    for dx,dy in d:
      nx,ny  =x+dx,y+dy
      if nx < 0 or nx >= h or ny < 0 or ny >=w :
        continue
      else:
        if maze[nx][ny] == ".":
          query.append((nx,ny,nm))
        else:
          ans = max(ans,nm)
          query = []
          break
          
  
  
  print(ans)
solve()

### FIXED CODE ###


from collections import deque
def solve():
  h,w = (int(i) for i in input().split())
  maze = ["0"*(w+2)]
  for i in range(h):
    maze.append("0"+input()+"0")
  maze.append("0"*(w+2))
  black = deque([])
  count = 0
  visit = [[False]*(w+2) for _ in range(h+2)]
  
  for i in range(h+2):
    for j in range(w+2):
      if maze[i][j] == "#":
        black.append((0,i,j)) #move,h,w

  d = [(0,1),(1,0),(-1,0),(0,-1)]
  ans = 0
  
  while count != h*w:
    move,y,x = black.popleft()
    #print(move,y,x)
    if visit[y][x]:
      continue
    else:
      visit[y][x] = True
      count += 1
      for dy,dx in d:
        ny,nx = y+dy,x+dx
        if visit[ny][nx]:
          continue
        elif maze[ny][nx] ==".":
          black.append((move+1,ny,nx))
  print(move)
          

    
solve()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,K = list(map(int,input().split()))
target =[]
i=3
x = i/2*K
while x <= 3*N:
    if x == int(x):
        target.append(int(x))
    i += 1
    x = i/2*K
count = 0
if K%2 == 0:
    A = list(range(K//2,N+1,K//2))
else:
    A = list(range(K,N+1,K))


for trg in target:
    for a in A:
        for b in range((a//K+1)*K-a,N+1,K):
            c = trg - a - b
            #print(a,b,c,target)
            if  0 < c <= N  and (b+c)%K == 0 and (c+a)%K ==0:
                #print(a,b,c)
                count += 1
print(count)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N,K=list(map(int,input().split()))
if K%2 == 0:
    A = list(range(K//2,N+1,K))
    B = list(range(K,N+1,K))
else:
    A = list(range(K,N+1,K))
    B = []
print(len(A)**3+len(B)**3)
### BUGGY CODE ###

import math
N = 10**9+7
n = int(input())
a = list(map(int,input().split()))

ans = 0

po = 1
for i in range(61):
    sum=0
    for j in range(n):
        sum+=(a[j]>>i) & 1
    ans+=sum*(n-sum)*po
    ans%=N
    po*=2
    po%=N
print(ans)


### FIXED CODE ###

import numpy as np
N = 10**9+7
n = int(input())
a = np.array(input().split(), np.int64)

ans = 0

po = 1
for i in range(61):
    bit = (a>>i) & 1
    s=np.count_nonzero(bit)
    ans+=s*(n-s)%N*po
    ans%=N
    po*=2
    po%=N
print(ans)
### BUGGY CODE ###

import bisect

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
B.sort()
C.sort()
cnt = 0
for a in A:
  pos_b = bisect.bisect_right(B, a)
  for pb in range(pos_b, N):
    pos_c = bisect.bisect_right(C, B[pb])
    cnt += N-pos_c
    if pos_c == N-1:
      break
print(cnt)

### FIXED CODE ###

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

nums = []
for idx in range(N):
  nums.append((1, A[idx]))
  nums.append((2, B[idx]))
  nums.append((3, C[idx]))
nums.sort(key=lambda x:(x[1], -x[0]))
sum_a = 0
sum_b = 0
sum_c = 0
for idx in range(3*N):
  if nums[idx][0] == 1:
    sum_a += 1
  elif nums[idx][0] == 2:
    sum_b += sum_a
  elif nums[idx][0] == 3:
    sum_c += sum_b
print(sum_c)
### BUGGY CODE ###

import numpy as np

n,m,q = map(int,input().split())
li = [[0 for i in range(n+1)]for j in range(n+1)]

for i in range(m):
    l,r = map(int,input().split())
    li[l][r] += 1
    li[r][l] += 1

li = np.array(li)

for i in range(q):
    l,r = map(int,input().split())
    print(np.sum(li[l:r+1,l:r+1])//2)

### FIXED CODE ###

import numpy as np

n,m,q = map(int,input().split())
li = [[0 for i in range(n+1)]for j in range(n+1)]

for i in range(m):
    l,r = map(int,input().split())
    li[l][r] += 1

li = np.array(li)
c = np.cumsum(li,axis=1).cumsum(axis=0).tolist()

for i in range(q):
    l,r = map(int,input().split())
    l -= 1
    point = c[r][r]
    point -= c[r][l]
    point -= c[l][r]
    point += c[l][l]
    print(point)
### BUGGY CODE ###

import sys

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

input = sys.stdin.readline

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

uf = UnionFind(N)
for a, b in relations:
    uf.union(a, b)

max_n = 0
# print(uf.all_group_members())
for i, members in uf.all_group_members().items():
    # print(members)
    max_n = max(max_n, len(members))

print(max_n)

### FIXED CODE ###

import sys
from collections import deque

input = sys.stdin.readline

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

ans = 0
visited = set()
for i in range(N):
    q = deque()
    q.append(i)
    start = len(visited)
    while q:
        pos = q.popleft()
        if pos in visited:
            continue
        visited.add(pos)
        for n_pos in relations[pos]:
            if n_pos in visited:
                continue
            q.appendleft(n_pos)
    end = len(visited)
    ans = max(ans, end - start)

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

a = input()
l = list(map(int,input().split()))
ans = 1

for i in l:
    ans *= i
if ans > 10**18:
    ans=-1
print(ans)

### FIXED CODE ###


a = input()
l = list(map(int,input().split()))
ans = 1
if 0 in l:
    print(0)
    exit()
for i in l:
    ans *= i
    if ans>10**18:
        print(-1)
        exit()
if ans > 10**18:
    ans=-1
print(ans)
### BUGGY CODE ###


import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

import sys
def input():
	return sys.stdin.readline().strip()


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

graph = [[] for _ in range(N)]
depth = [0 for _ in range(N)]
parent_list = [[] for _ in range(N)]
parent = [-1 for _ in range(N)]

for i in range(N - 1 + M):
	A, B = list(map(int, input().split()))
	A -= 1
	B -= 1
	graph[A].append(B)
	parent_list[B].append(A)

for i in range(N):
	if len(parent_list[i]) == 0:
		root = i
		break

que = deque([])
que.append(root)

while len(que) > 0:
	node = que.popleft()
	if len(graph[node]) > 0:
		for edge in graph[node]:
			depth[edge] = depth[node] + 1
			que.append(edge)

for i in range(N):
	parent_depth = -1
	parent_node = -1
	if len(parent_list[i]) > 0:
		for p in parent_list[i]:
			if depth[p] > parent_depth:
				parent_depth = depth[p]
				parent_node = p
		parent[i] = parent_node

#print(parent_list, depth)

for i in range(N):
	print(parent[i] + 1)

### FIXED CODE ###


import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

import sys
def input():
	return sys.stdin.readline().strip()


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

graph = [[] for _ in range(N)]
depth = [0 for _ in range(N)]
parent_list = [[] for _ in range(N)]
parent_num = [0 for _ in range(N)]
parent = [-1 for _ in range(N)]

for i in range(N - 1 + M):
	A, B = list(map(int, input().split()))
	A -= 1
	B -= 1
	graph[A].append(B)
	parent_list[B].append(A)
	parent_num[B] += 1

for i in range(N):
	if len(parent_list[i]) == 0:
		root = i
		break

que = deque([])
que.append(root)

while len(que) > 0:
	node = que.popleft()
	if len(graph[node]) > 0:
		for edge in graph[node]:
			depth[edge] = depth[node] + 1
			parent_num[edge] -= 1
			if parent_num[edge] == 0:
				que.append(edge)

for i in range(N):
	parent_depth = -1
	parent_node = -1
	if len(parent_list[i]) > 0:
		for p in parent_list[i]:
			if depth[p] > parent_depth:
				parent_depth = depth[p]
				parent_node = p
		parent[i] = parent_node

#print(parent_list, depth)

for i in range(N):
	print(parent[i] + 1)
### BUGGY CODE ###

n,s = map(int, input().split())
a = list(map(int, input().split()))

MOD = 998244353

dp = [[0]*(s+1) for i in range(n+1)] #動的計画法を用いる
dp[0][0] = 1

for i in range(n):
    for ss in range(s+1):
        if(ss >= a[i]):
            dp[i+1][ss] = (dp[i][ss]*2%MOD + dp[i][ss-a[i]])%MOD #非常に大きな数になると考えられるため先にMOD計算を行う
        else:
            dp[i+1][ss] = dp[i][ss]*2 % MOD

print(dp[n][s])

### FIXED CODE ###

n,s = map(int, input().split())
a = list(map(int, input().split()))

MOD = 998244353

dp = [[0]*(s+1) for i in range(n+1)] #動的計画法を用いる
dp[0][0] = 1

for i in range(n):
    for ss in range(s+1):
        if(ss >= a[i]):
            dp[i+1][ss] = (dp[i][ss]*2 + dp[i][ss-a[i]])%MOD #非常に大きな数になると考えられるため先にMOD計算を行う
        else:
            dp[i+1][ss] = dp[i][ss]*2 % MOD

print(dp[n][s])
### BUGGY CODE ###

def main():
    N, M  = [int(i) for i in input().split()]
    S  = [int(i) for i in input()]
    cur = [0]
    while cur:
        nxt = []
        for loc in cur:
            if loc == N:
                a = []
                while loc > 0:
                    w = S[loc]
                    loc -= w
                    a.append(w)
                return ' '.join(str(j) for j in reversed(a))
            for i in range(1, M + 1):
                nloc = loc + i
                if nloc > N or S[nloc]:
                    continue
                S[nloc] = i
                nxt.append(nloc)
        cur = nxt
    return '-1'


print(main())


### FIXED CODE ###

def main():
    N, M  = [int(i) for i in input().split()]
    S  = [int(i) for i in input()]
    loc = N
    a = []
    while loc:
        for i in range(min(loc, M), 0, -1):
            if S[loc - i] == 1:
                continue
            a.append(i)
            loc -= i
            break
        else:
            return '-1'
    return ' '.join(str(i) for i in reversed(a))


print(main())
### BUGGY CODE ###

n, k = list(map(int,input().split()))
l = list(map(int,input().split()))
dp = [10**10]*n
dp[0] = 0
dp[1] = abs(l[0] - l[1])
for i in range(2,n):
    for j in range(i-1,max(0,i-k)-1,-1):
        tem = dp[j] + abs(l[i] - l[j])
        if tem<dp[i]:
            dp[i] = tem
    
print(dp[n-1])
#print(dp)    
    

### FIXED CODE ###

n, k = list(map(int,input().split()))
l = list(map(int,input().split()))
dp = [10**9]*n
dp[0] = 0
dp[1] = abs(l[0] - l[1])
for i in range(2,n):
    for j in range(i-1,max(0,i-k)-1,-1):
        tem = dp[j] + abs(l[i] - l[j])
        if tem<dp[i]:
            dp[i] = tem
    
print(dp[n-1])
### BUGGY CODE ###

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

pairs = [[] for _ in range(N + 1)]
for _ in range(M):
    input_list = list(map(int, input().split()))
    pairs[input_list[0]].append(input_list[1])
    pairs[input_list[1]].append(input_list[0])

ans = [0 for _ in range(N + 1)]
n_ans = 0   # ansを埋めた回数 -> N-1になったら終了
done = [1] # 探索済リスト

n = 1
while n_ans < N - 1:
    for m in pairs[n]:
        if m not in done:
            done.append(m)
            ans[m] = n
            n_ans += 1
    n = m

print('Yes')
for i in range(2, N + 1):
    print(ans[i])

### FIXED CODE ###

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

pairs = [[] for _ in range(N + 1)]  # pairs[i]:iと直接つながっている部屋のリスト
for _ in range(M):
    input_list = list(map(int, input().split()))
    pairs[input_list[0]].append(input_list[1])
    pairs[input_list[1]].append(input_list[0])

ans = [0 for _ in range(N + 1)]
n_ans = 0   # ansを埋めた回数 -> N-1になったら終了
done = [False for _ in range(N + 1)]  # 探索済リスト
todo = [1]

while n_ans < N - 1:
    for n in todo:
        for m in pairs[n]:
            if not done[m]:
                done[m] = True
                ans[m] = n
                n_ans += 1
                todo.append(m)

print('Yes')
for i in range(2, N + 1):
    print(ans[i])
### BUGGY CODE ###

#089_D
h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
idx = {}
for x in range(0, h):
    for y in range(0, w):
        idx[a[x][y]] = (x, y)
        
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    cur = l
    ans = 0
    while cur != r:
        cur_x, cur_y = idx[cur]
        to_x, to_y = idx[cur + d]
        ans += abs(cur_x - to_x) + abs(cur_y - to_y)
        cur += d
    print(ans)

### FIXED CODE ###

#089_D
h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
idx = {}
for x in range(0, h):
    for y in range(0, w):
        idx[a[x][y]] = (x, y)
        
dp = [0 for _ in range(h*w+1)]
for i in range(0, h*w+1):
    if i <= d:
        continue
    x, y = idx[i]
    x_, y_ = idx[i-d]
    dp[i] = dp[i-d] + abs(x-x_) + abs(y-y_)
        
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(dp[r] - dp[l])
### BUGGY CODE ###

h,w = map(int,input().split())
s = [input() for _ in range(h)]
u1 = [[0 for _ in range(w)] for _ in range(h)]
u2 = [[0 for _ in range(w)] for _ in range(h)]
d1 = {}
d2 = {}

idx = 1
cnt = 0
for i in range(h):
    flag = False
    for j in range(w):
        if s[i][j] == ".":
            flag = True
            u1[i][j] = idx
            cnt += 1
        elif flag:
            d1[idx] = cnt
            cnt = 0
            idx += 1
            flag = False  
    if flag:
        d1[idx] = cnt
        cnt = 0
        idx += 1

idx = 1
cnt = 0
for j in range(w):
    flag = False
    for i in range(h):
        if s[i][j] == ".":
            flag = True
            u2[i][j] = idx
            cnt += 1
        elif flag:
            d2[idx] = cnt
            cnt = 0
            idx += 1
            flag = False  
    if flag:
        d2[idx] = cnt
        cnt = 0
        idx += 1

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            ans = max(ans, d1[u1[i][j]]+d2[u2[i][j]]-1)
print(ans)

### FIXED CODE ###

h,w = map(int,input().split())
s = [input() for _ in range(h)]
u1 = [[0 for _ in range(w)] for _ in range(h)]
u2 = [[0 for _ in range(w)] for _ in range(h)]
d1 = {}
d2 = {}

idx = 1
cnt = 0
for i in range(h):
    flag = False
    for j in range(w):
        if s[i][j] == ".":
            flag = True
            u1[i][j] = idx
            cnt += 1
        elif flag:
            d1[idx] = cnt
            cnt = 0
            idx += 1
            flag = False  
    if flag:
        d1[idx] = cnt
        cnt = 0
        idx += 1

idx = 1
cnt = 0
for j in range(w):
    flag = False
    for i in range(h):
        if s[i][j] == ".":
            flag = True
            u2[i][j] = idx
            cnt += 1
        elif flag:
            d2[idx] = cnt
            cnt = 0
            idx += 1
            flag = False  
    if flag:
        d2[idx] = cnt
        cnt = 0
        idx += 1

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            ans = max(ans, d1[u1[i][j]]+d2[u2[i][j]]-1)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
s = list(str(input()))
q = int(input())

def segfunc(x,y):
    return x | y

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]={init_val[i]}
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = set()

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

init(s)
#print(seg)

for i in range(q):
    t, x, y = map(str, input().split())
    if t == '2':
        l = int(x)-1
        r = int(y)-1
        print(len(query(l, r+1)))
    else:
        i = int(x)-1
        c = {y}
        update(i, c)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
s = list(str(input()))
q = int(input())

s = [ord(c)-ord('a') for c in s]

#def segfunc(x,y):
    #return x | y

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]={init_val[i]}
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=seg[2*i+1] | seg[2*i+2]

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = seg[k*2+1] | seg[k*2+2]

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = res | seg[p]
        if q&1 == 1:
            res = res | seg[q]
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = res | seg[p]
    else:
        res = (res | seg[p]) | seg[q]
    return res

#####単位元######
ide_ele = set()

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

init(s)
#print(seg)

for i in range(q):
    t, x, y = map(str, sys.stdin.readline().split())
    if t == '2':
        l = int(x)-1
        r = int(y)-1
        print(len(query(l, r+1)))
    else:
        i = int(x)-1
        c = {ord(y)-ord('a')}
        update(i, c)
### BUGGY CODE ###

[N,W]=[int(x) for x in input().split()]
weight_and_value=[[0,0]]
for i in range(N):
  weight_and_value.append([int(x) for x in input().split()]) 
dp=[[0 for i in range(W+1)] for i in range(N+1)]
for i in range(1,N+1):
  for w in range(W+1):
    if weight_and_value[i][0]>w:
      dp[i][w]=dp[i-1][w]
    else:
      dp[i][w]=max(dp[i-1][w],dp[i-1][w-weight_and_value[i][0]]+weight_and_value[i][1])

print(dp[N][W])
  

### FIXED CODE ###

import numpy as np
[N,W]=[int(x) for x in input().split()]
dp=np.zeros([N+1,W+1],dtype=int)
for i in range(1,N+1):
  w, v=map(int,input().split())
  dp[i][:w]=dp[i-1][:w]
  dp[i][w:]=np.maximum(dp[i-1][w:],dp[i-1][:W-w+1]+v)
print(dp[N][W])