Harryxun/stf_run huggingface dataset:
N,M = map(int, input().split())

from scipy.sparse import lil_matrix
from scipy.sparse.csgraph import depth_first_order,bellman_ford
import numpy as np
from time import process_time as timer

G = lil_matrix((N,N), dtype='i4')

for i in range(M):
  a,b,c = map(int, input().split())
  G[a-1,b-1] = -c

# remove nodes unreachable from goal or start
n1 = set(depth_first_order(G, 0, return_predecessors=False))
n2 = set(depth_first_order(G.T, N-1, return_predecessors=False))
n = n1&n2
# N = len(nodes)
# nodes.sort()
# G = G[np.ix_(nodes,nodes)]

try:
  dist = bellman_ford(G,list(n))
  print(-int(dist[0,N-1]))
except NegativeCycleError:
  print('inf')

### FIXED CODE ###



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

from collections import defaultdict
neighbor = defaultdict(list)
Rneighbor = defaultdict(list)
edges = []
for i in range(M):
  a,b,c = map(int, input().split())
  a,b = a-1, b-1
  edges += [(a,b,c)]
  neighbor[a].append(b)
  Rneighbor[b].append(a)

# only vertices that are reachable from 1 or N
v1 = set()
v1.add(0)
stack = [0]
while stack:
  v = stack.pop()
  for u in neighbor[v]:
    if u not in v1:
      v1.add(u)
      stack.append(u)

vn = set()
vn.add(N-1)
stack = [N-1]
while stack:
  v = stack.pop()
  for u in Rneighbor[v]:
    if u not in vn:
      vn.add(u)
      stack.append(u)

V = v1 & vn

edges = [(a,b,c) for a,b,c in edges if a in V and b in V]
score = [float('-inf')]*N
score[0] = 0

updated = True
i = 0

positive_cycle = False

while updated:
  if i == len(V):
    positive_cycle = True
    break

  updated = False
  for a,b,w in edges:
    if score[b] < score[a] + w:
      score[b] = score[a] + w
      updated = True
  i += 1

if positive_cycle:
  print('inf')
else:
  print(score[N-1])
n=input()
print((n+1)//2)

### FIXED CODE ###

n = int(input())
print((n + 1) // 2)
num = input()
print(num + (num*num) + (num*num*num))

### FIXED CODE ###

num = int(input())
print(num + (num*num) + (num*num*num))
a=input()
if a=0:
  print(a)
else:
  print(a*2)


### FIXED CODE ###

a=int(input())
b=int(a/2)
if b*2==a:
  print(a)
else:
  print(a*2)
s = input()
k = int(input())

if k == 1:
    ans = list(s)[0]
else:
    for i, j in enumerate(list(s)):
        if j != '1' and i < k:
            ans = j
            break
        elif i >=k :
            ans = '1'
            break
        else:
            continue
print(ans)

### FIXED CODE ###

s = input()
k = int(input())

if k == 1 or len(s) == 1:
    ans = list(s)[0]
else:
    ans = None
    for i, j in enumerate(list(s)):
        if i < k-1:
            if j != '1':
                ans = j
                break
        elif i == k-1:
            ans = j           
            break
        else:
            continue
print(ans)
count = {} #a~zの出現回数を記録
for i in range(26):
    count[(i)] = 0

text = []
while True:
    try:
        text = raw_input()
    except:
        break
    for i in range(len(text)):
        if(ord(text[i]) >= ord('a') and ord(text[i]) <= ord('z')):
            count[(ord(text[i]))-ord('a')] += 1
        if(ord(text[i]) >= ord('A') and ord(text[i]) <= ord('Z')):
            count[(ord(text[i]))-ord('A')] += 1

#出現回数の表示
for i in range(26):
    print '%s : %d' %(unichr(i+ord('a')), count[(i)])

### FIXED CODE ###

count = {}
for i in range(26):
    count[(i)] = 0

while True:
    try:
        x = raw_input()
    except:
        break
    for i in range(len(x)):
        if(ord('a') <= ord(x[i]) and ord(x[i]) <= ord('z')):
            count[(ord(x[i])-ord('a'))] += 1
        elif(ord('A') <= ord(x[i]) and ord(x[i]) <= ord('Z')):
            count[(ord(x[i])-ord('A'))] += 1

for i in range(26):
    print '%s : %d' %(chr(i+ord('a')), count[(i)])
exit(0)
N, K = map(int, input().split())
A = list(map(int, input().split()))
# B = [0 for i in range(N + 1)]
B=[]
for a in A:
    B[a] += 1
# nums = [b for b in B if b > 0]
nums=B.sort()
n = len(nums)
print(0 if n<=K else sum(nums[:n - K]))

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
B = [0 for i in range(N + 1)]

for a in A:
    B[a] += 1
nums = [b for b in B if b > 0]
nums.sort()
n = len(nums)
print(0 if n<=K else sum(nums[:n - K]))
N, M = map(int, input().split())
a, b, c, d = [],[],[],[]

for i in range(N):
  ai, bi = map(int, input().split())
  a.append(ai)
  b.append(bi)
#  print(a, b)
for j in range(M):
  cj, dj = map(int, input().split())
  c.append(cj)
  d.append(dj)
  
#print(a,b,c,d)
  
for i in range(N):
  dist, min_dist = 0, INF
  ans = 1
  for j in range(M):
    dist = abs(c[j] - a[i]) + abs(d[j] - b[i])
    if dist < min_dist:
      ans = j+1
      min_dist = dist
#    print("ai:{}, bi:{}, cj:{}, dj:{}, dist:{}, ans:{}".format(a[i], b[i], c[j], d[j], dist, ans))
#    print("i:{}, j:{}, dist:{}, min_dist:{}, ans:{}".format(i, j, dist, min_dist, ans))
#    min_dist = min(dist, min_dist)
  print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
a, b, c, d = [],[],[],[]

for i in range(N):
  ai, bi = map(int, input().split())
  a.append(ai)
  b.append(bi)
#  print(a, b)
for j in range(M):
  cj, dj = map(int, input().split())
  c.append(cj)
  d.append(dj)
  
#print(a,b,c,d)
  
for i in range(N):
  dist, min_dist = 0, 10**9
  ans = 1
  for j in range(M):
    dist = abs(c[j] - a[i]) + abs(d[j] - b[i])
    if dist < min_dist:
      ans = j+1
      min_dist = dist
#    print("ai:{}, bi:{}, cj:{}, dj:{}, dist:{}, ans:{}".format(a[i], b[i], c[j], d[j], dist, ans))
#    print("i:{}, j:{}, dist:{}, min_dist:{}, ans:{}".format(i, j, dist, min_dist, ans))
#    min_dist = min(dist, min_dist)
  print(ans)
s = [int(a) for a in input()[::-1]]

m = 2019
n = len(S)

f = 0

p = 1

X = [0] * 2019

X[0] = 1

q = 0

for a in S:
    f = (f + a * p) % m
    q += X[f]
    
    X[s] += 1
    
    p = p * 10 % m
 

print(q)

### FIXED CODE ###

S = [int(a) for a in input()[::-1]]
m = 2019
N = len(S)
s = 0
p = 1
X = [0] * 2019
X[0] = 1
ans = 0
for a in S:
    s = (s + a * p) % m
    ans += X[s]
    X[s] += 1
    p = p * 10 % m
 
print(ans)
S,T=input().split()
A,B=map(int,input().split())
U = input()
if U == S:
    print (f"{A-1} {B}")
else:
    print(f"{A} {B-1}")


### FIXED CODE ###

S,T=input().split()
A,B=map(int,input().split())
U = input()
if U == S:
    print('{} {}'.format(A-1, B))
else:
    print('{} {}'.format(A, B-1))
N,M = map(int, input().split())
A = []
quantity = 0
price = 0

for i in range(N):
    a = list(map(int, input().split()))
    A.append(a)
A = sorted(A)
for i in range(M):
    quantity += A[i][1]
    if quantity <= M:
        price += A[i][0]*A[i][1]
    else:
       price += A[i][0]*(M-(quantity-A[i][1]))
       break
print(price)

### FIXED CODE ###

N,M = map(int, input().split())
A = []
quantity = 0
price = 0

for i in range(N):
    a = list(map(int, input().split()))
    A.append(a)
A = sorted(A)
for i in range(M):
    quantity += A[i][1]
    if quantity < M:
        price += A[i][0]*A[i][1]
    else:
       price += A[i][0]*(M-(quantity-A[i][1]))
       break
print(price)
s = int(input()) 

dict={}
num_list = list(map(int, input().split()))

length=len(num_list)
count=[0]*(s+1)
for i in range(length):
    count[num_list[i]]+=1
    dict[num_list[i]]=count[num_list[i]]
    
#print(dict)


sum=0
count=0
n = int(input()) 
for i in range(n):
    a,b = map(int, input().split())  
    if dict.get(a)!=None:
        if dict.get(b)!=None:
            count=dict[b]
            dict[b]=dict[a]+dict[b]
        else:
            dict[b]=dict[a]
        dict[a]=0
    else:
        pass
    #print(dict)
    for k, v in dict.items():
        sum+=k*v
    print(sum)
    sum=0

   


### FIXED CODE ###

s = int(input()) 

dict={}
num_list = list(map(int, input().split()))

length=len(num_list)
count=[0]*(s+1000)
for i in range(length):
    count[num_list[i]]+=1
    dict[num_list[i]]=count[num_list[i]]
    
sum=0
#print(dict)
for k, v in dict.items():
    sum+=k*v
#print(dict)
#print(sum)

count=0
d=0
n = int(input()) 
for i in range(n):
    a,b = map(int, input().split())  
    if dict.get(a)!=None:
        d=(b-a)*dict[a]
        #print("d:{}".format(d))
        if dict.get(b)!=None:
            count=dict[b]
            dict[b]=dict[a]+dict[b]
        else:
            dict[b]=dict[a]
        dict[a]=0
        sum+=d
        
        #print(dict)
        
    else:
        pass
    d=0
    print(sum)
    #print()
x,t = map(int,input().split())

print(max(x - t),0)

### FIXED CODE ###

x,t = map(int,input().split())
 
print(max(x - t,0))
import re
n,m = map(int, input().split())
a = [input().strip() for i in range(n)]
b = [input().strip() for i in range(m)]

mc = n-m+1
ans = False
for ai in range(0, mc):
  if(ans):
    break
  ind = [x.start() for x in re.finditer(b[0], a[ai])]
  for i in ind:
    if(ans):
      break
    for bi in range(0, mc):
      print(bi,a[ai+bi+1][i:i+m], b[bi+1])
      if(a[ai+bi+1][i:i+m] != b[bi+1]):
        break
      if(bi==mc-1):
        ans = True
if(ans):
  print('Yes')
else:
  print('No')

### FIXED CODE ###

import re
n,m = map(int, input().split())
a = [input().strip() for i in range(n)]
b = [input().strip() for i in range(m)]

mc = n-m+1
ans = False
for ai in range(0, mc):
  if(ans):
    break
  ind = [x.start() for x in re.finditer(b[0], a[ai])]
  if(m==1)and(len(ind)>0):
    ans=True
    break  
  for i in ind:
    if(ans):
      break
    for bi in range(1, m):
      if(a[ai+bi][i:i+m] != b[bi]):
        break
      if(bi==m-1):
        ans = True
        break
if(ans):
  print('Yes')
else:
  print('No')
s = input()
print(700　+ 100*s.count('o')

### FIXED CODE ###

s=input()
print(700+int(s.count("o"))*100)
n=int(input())
s=input()
for i in range(len(s)):
  val=ord(s[i])
  val-=65
  val=(val+n)%26
  val+=65
  s[i]=chr(val)
print(s)

### FIXED CODE ###

n=int(input())
s=input()
val=0
res=""
for i in range(len(s)):
  val=ord(s[i])
  val-=65
  val=(val+n)%26
  val+=65
  res+=chr(val)
print(res)
lis=list(input().split( ))
 
for i,x in enumerate(lis):
  if x == 0:
    a = i
print a

### FIXED CODE ###

lis=list(map(int,input().split()))
for i, x in enumerate(lis):
  if x == 0:
    a = i+1
print (a)
# coding: utf-8
a=int(input())
b=int(input())
c=int(input())
X=int(input())
l1=X//a
l2=X//b
l3=X//c
ans=0
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            #p=a*i+b*j+c*k
            #print(p)
            if 500*i+100*j+50*k==X:
                ans+=1
                
print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!
l = []

for i in range(4):
    l.append(int(input()))

x = l[3]
ans = 0
for i in range(l[0]+1):
    for j in range(l[1]+1):
        for k in range(l[2]+1):
            if 500 * i + 100 * j + 50 * k == x:
                ans += 1
                
print(ans)
n = int(input())
m = 0

for i in rane(n+1):
  if n%3 != 0 and n%5 != 0:
    m += i

print(m)



### FIXED CODE ###

n = int(input())
m = 0

for i in range(n+1):
  if i%3 != 0 and i%5 != 0:
    m += i

print(m)
N = int(input())
H = list(map(int, input().split()))
ans = "Yes"
for i in range(N - 1):
  if H[i] > H[i + 1]:
    H[i] = H[i] - 1
    if H[i] > H[i + 1]:
      ans = "No"
    if max(H[:i]) != H[i]:
      ans = "No"
print(ans)

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
ans = "Yes"
for i in range(0, N - 1):
  diff = H[i + 1] - H[i]
  if diff >= 1:
    H[i + 1] -= 1
  elif diff < 0:
    ans = "No"
print(ans)
cdef gcd(a,b):
    if b<a:a,b=b,a
    r=b%a
    return a if r==0else gcd(a,r)
k=int(input())+1
print(sum(gcd(c,gcd(a,b))for a in range(1,k)for b in range(1,k)for c in range(1,k)))

### FIXED CODE ###

from math import*
r=range(1,int(input())+1)
print(sum(gcd(gcd(a,b),c)for a in r for b in r for c in r))
import numpy as np

n, m = map(int, raw_input().split())
g = []
for i in range(m):
    g.append(map(int, raw_input().split()))

graph = {}
for i in g:
    if i[0] not in graph:
        graph[i[0]] = [[i[1], i[2]]]
    else:
        graph[i[0]].append([i[1], i[2]])

table = np.zeros(n + 1) + 0.5
table[1] = 0
fp = [1]
for i in range(n):
    for k in fp:
        if k in graph.keys():
            for j in graph[k]:
                if table[j[0]] < table[k] + j[1]:
                    table[j[0]] = table[k] + j[1]
                    if j[0] != n and fp not in [j[0]]:
                        fp.append(j[0])
                if table[j[0]] == 0.5:
                    table[j[0]] = table[k] + j[1]
                    if j[0] != n:
                        fp.append(j[0])
max = int(table[n])
fp.append(n)
flag = 0
for i in range(3):
    for k in fp:
        if k in graph.keys():
            for j in graph[k]:
                if table[j[0]] < table[k] + j[1]:
                    table[j[0]] = table[k] + j[1]
                    fp.append(j[0])
                if table[j[0]] == 0.5:
                    table[j[0]] = table[k] + j[1]
                    if j[0] != n:
                        fp.append(j[0])
                if max < int(table[n]):
                    print"inf"
                    flag = 1
                    break
        if flag == 1:
            break

    if flag == 1:
        break
if flag != 1:
    print int(table[n])


### FIXED CODE ###

a, b, c = map(int, raw_input().split())

print "Yes" if c >= a and c <= b else "No"
n, m = map(int, input().split())
g = [set() for _ in range(n)]

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def find(s, t):
    global g
    visited = [0] * n

    def dfs(i):
        visited[i] = 1
        if i == t:
            return True
        for f in g[i]:
            if not visited[f]:
                if dfs(f):
                    return True
        return False

    return dfs(s)


q = int(input())
while q:
    s, t = map(int, input().split())
    print('yes' if find(s, t) else 'no')
    q -= 1

### FIXED CODE ###

n, m = map(int, input().split())
g = [set() for _ in range(n)]
group_ids = [0] * n

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def search(s, gid):
    global g, group_ids
    queue = set(g[s])
    group_ids[s] = gid

    while queue:
        i = queue.pop()
        if not group_ids[i]:
            group_ids[i] = gid
            queue.update(g[i])


gid = 1
for i in range(n):
    if group_ids[i]:
        continue
    search(i, gid)
    gid += 1

q = int(input())
while q:
    s, t = map(int, input().split())
    gs, gt = group_ids[s], group_ids[t]
    print('yes' if gs and gt and gs == gt else 'no')
    q -= 1
s = input()[::-1]
t = input()[::-1]
for i,c in enumerate(s):
  if c == t[0] and (i+len(t) < len(s)):
    for j in range(len(t)):
      if t[j] != s[i+j] and s[i+j] != '?':
        break
    else:
      for j in range(len(t)):
        s[i+j] =  t[j]
      print(s.replace('?', 'a')[::-1])
      break
else:
  print('UNRESTORABLE')



### FIXED CODE ###

s = input()[::-1]
t = input()[::-1]
for i,c in enumerate(s):
  if (c == t[0] or c == '?') and (i+len(t) < len(s)+1):
    for j in range(len(t)):
      if t[j] != s[i+j] and s[i+j] != '?':
        break
    else:
      str_list = list(s)
      for j in range(len(t)):
        str_list[i+j] =  t[j]
      s = ''.join(str_list)
      print(s.replace('?', 'a')[::-1])
      break
else:
  print('UNRESTORABLE')
# 鍵の種類は12だからdfs で行けそう
N, M = map(int, input().split())
A = []
C = []
for i in range(M):
    a, b = map(int, input().split())
    c = set(list(map(int, input().split())))
    A.append(a)
    C.append(c)

def dfs(i, sum, box):
    global answer
    if i == M:
        if len(box) == N:
            answer = min(answer, sum)
    else:
        dfs(i+1, sum, box)
        dfs(i+1, sum+A[i], box|C[i])

INF = 10 ** 7
answer = INF
box = set()
dfs(0, 0, box)
#print(A)
#print(C)
if answer == INF:
    print(-1)
else:
    print(answer)

### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    b_cnt = 2 ** N #箱の数は最大12個
    INF = 10 ** 9
    dp = [INF] * b_cnt
    dp[0] = 0

    for i in range(M):
        a, b = map(int, input().split())
        c = sum([2 ** (int(x)-1) for x in list(input().split())])
        for j in range(b_cnt):
            if dp[j|c] > dp[j] + a:
                dp[j|c] = dp[j] + a

    if dp[-1] == INF:
        print(-1)
    else:
        print(dp[-1])

if __name__ == '__main__':
    main()
import sys

R, C, K = map(int, input().split())
item = [[0]*C for _ in range(R)]
for _ in range(K):
    r, c, v = map(int, sys.stdin.readlines().split())
    item[r-1][c-1] = v

DP = [[[0, 0, 0, 0] for _ in range(C)] for _ in range(R)]

DP[0][0][1] = item[0][0]

for i in range(R):
    for j in range(C):
        for k in range(4):
            if i > 0:  # 前の行から
                DP[i][j][0] = max(DP[i][j][0], max(DP[i-1][j]))  # 取らない
                DP[i][j][1] = max(DP[i][j][1], max(DP[i-1][j])+item[i][j])  # 取る

            if j > 0:  # 前の列から
                DP[i][j][k] = max(DP[i][j][k], DP[i][j-1][k])  # 取らない
                if k >= 1:
                    DP[i][j][k] = max(DP[i][j][k], DP[i][j-1][k-1]+item[i][j])  # 取る

print(max(DP[R-1][C-1]))

### FIXED CODE ###

import sys

R, C, K = map(int, input().split())
item = [[0] * (C + 1) for _ in range(R + 1)]  # dp配列と合わせるために, 0行目, 0列目を追加している.
for s in sys.stdin.readlines():
    r, c, v = map(int, s.split())
    item[r][c] = v

dp = [[[0] * (C + 1) for _ in range(R + 1)] for _ in range(4)]
for i in range(R + 1):
    for j in range(C + 1):
        for k in range(4):
            here = dp[k][i][j]
            # 次の行に移動する場合
            if i + 1 <= R:
                # 移動先のアイテムを取らない場合
                dp[0][i + 1][j] = max(dp[0][i + 1][j], here)
                # 移動先のアイテムを取る場合
                dp[1][i + 1][j] = max(dp[1][i + 1][j], here + item[i + 1][j])
            # 次の列に移動する場合
            if j + 1 <= C:
                # 移動先のアイテムを取らない場合
                dp[k][i][j + 1] = max(dp[k][i][j + 1], here)
                # 現在のkが3未満のときのみ, 移動先のアイテムを取ることが可能
                if k < 3:
                    dp[k + 1][i][j + 1] = max(dp[k + 1][i][j + 1], here + item[i][j + 1])
ans = 0
for k in range(4):
    ans = max(ans, dp[k][-1][-1])
print(ans)
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0
inf = float("inf")

def dpp(n):
    for i in range(2,n+1):
        if a[i] = 0:
            dp[i] = 0
        else:
            dp[i] = dp[i-1]+dp[i-2]
    return dp[n]

N,M = I()
a = [1]*(N +1)
for i in range(M):
    x = k()
    a[x] = 0

dp = [0]*(N+1)
if 1 in a:
    dp[1] = 0
    dp[0] = 1
else:
    dp[0] = dp[1] =1

print(dpp(N) % mod)


### FIXED CODE ###

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0
inf = float("inf")

def dpp(n):
    for i in range(2,n+1):
        if a[i] == 0:
            dp[i] = 0
        else:
            dp[i] = dp[i-1]+dp[i-2]
    return dp[n]

N,M = I()
a = [1]*(N +1)
for i in range(M):
    x = k()
    a[x] = 0

dp = [0]*(N+1)
if a[1] == 0:
    dp[1] = 0
    dp[0] = 1
else:
    dp[0] = dp[1] =1

print(dpp(N) % mod)
import numpy as np
n,k = map(int,input().split())

arr = list(map(int,input().split()))
s = [0 for i in range(n)]
temp = 0

ans = 0
for i in range(n):
    temp += arr[i]
    s[i] = temp

for i in range(1,k+1):
    upper = min(n,i)
    for j in range(upper+1):
        v = 0
        a = []
        for l in range(j):
            v += arr[l]
            a.append(arr[l])
        for l in range(1,i+1-j):
            v+= arr[-l]
            a.append(arr[-l])
        a.sort()
        # print(a,v)
        if k-i > 0:
            up = min(k-i-1,i)
            for l in range(up):
                if a[l] < 0:
                    v -= a[l]
                else:
                    break
        if v > ans:
            ans = v

print(ans)




### FIXED CODE ###

import numpy as np
n,k = map(int,input().split())

arr = list(map(int,input().split()))
s = [0 for i in range(n)]
temp = 0
ans = 0

for i in range(1,k+1):
    upper = min(n,i)
    for j in range(upper+1):
        v = 0
        a = []
        for l in range(j):
            v += arr[l]
            a.append(arr[l])
        for l in range(1,upper+1-j):
            v+= arr[-l]
            a.append(arr[-l])
        a.sort()
        # print(a,v)
        up = min(k-upper,i)
        for l in range(up):
            if a[l] < 0:
                v -= a[l]
            else:
                break
        if v > ans:
            ans = v

print(ans)
N,W = map(int,input().split())
value = [0]
weight = [0]
for i in range(N):
    v,w = map(int,input().split())
    value.append(v)
    weight.append(w)

dp = [[0]*(N+10) for _ in range(W+10)]

for w in range(1,W+2):
    for k in range(1,N+1):
        if weight[k] > w:
            dp[k][w] = dp[k-1][w]
        else:
            dp[k][w] = max(dp[k-1][w], value[k] + dp[k-1][w-weight[k]])
print(dp[N][W])



### FIXED CODE ###

N,W = map(int,input().split())
value = [0]
weight = [0]
for i in range(N):
    v,w = map(int,input().split())
    value.append(v)
    weight.append(w)

dp = [[0]*(W+3) for _ in range(N+3)]
for w in range(1,W+1):
    for k in range(1,N+1):
        if weight[k] > w:
            dp[k][w] = dp[k-1][w]
        else:
            #print(dp[k-1][w])
            dp[k][w] = max(dp[k-1][w], value[k] + dp[k-1][w-weight[k]])
print(dp[N][W])
N = int(input())
d = list(map(int, input().split()))
d.sort()
print(d[N/2] - d[N/2-1])
    

### FIXED CODE ###

import math
N = int(input())
d = list(map(int, input().split()))
d.sort()
tmp = math.floor(N/2)
print(d[tmp] - d[tmp-1])
import sys
input = sys.stdin.readline
N,M=map(int,input().split())
list1=list(map(int,input().split()))
listBC=[]
for _ in range(M):
  B,C=map(int,input().split())
  listBC+=[[C,B]]  
listBC.sort(reverse=True)
i=0
while min(list1)<listBC[i][0]:  
  list1.append(listBC[i][0]*listBC[i][1])
  for k in range(listBC[i][1]):
    list1.remove(min(list1))
  i+=1  
SUM=sum(list1)
print(SUM)

### FIXED CODE ###

N,M = map(int, input().split())
listA = list(map(int, input().split()))
listA.sort()
 
listBC = [list(map(int, input().split())) for i in range(M)]
listBC = sorted(listBC, key=lambda x: x[1], reverse=True)
countB = 0
 
for i in range(M):
  B, C = listBC[i][0], listBC[i][1]
  listA += [C]*B
  countB += B
  if countB >= N:
    break

listA.sort(reverse=True)
print(sum(listA[:N]))
s = str(input())
if s.count("R") = 3:
  print(3)
  elif s.count("R") = 2:
    print(2)
    elif s.count("R") = 1:
      print(1)
      else:
        print(0)

### FIXED CODE ###

s = input()
if s == "RRR":
  print(3)
if s == "SSS":
  print(0)
if s == "RRS":
  print(2)
if s == "SRR":
  print(2)
if s == "RSS":
  print(1)
if s == "SRS":
  print(1)
if s == "SSR":
  print(1)
if s == "RSR":
  print(1)
import numpy as np

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

sosu = []
count = 0

def loop(target, A):
  global count
  B = []
  flg = True
  for i in range(len(A)):
    if A[i] % target != 0:
      B.append(A[i])
    if target == A[i]:
      flg = False
  if flg:
    count+=1
  if len(B) == 1:
    count+=1
    return
  if len(B) == 0:
    return
  target = B.pop(0)
  loop(target, B)

target = A.pop(0)
loop(target, A)
print(count)

### FIXED CODE ###

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

m_a = max(A)+1
B = [0]*(m_a)

for i in A:
  B[i]+=1
  if B[i] == 1:
    for j in range(i*2, m_a, i):
      B[j]+=100
print(B.count(1))