Harryxun/stf_run huggingface dataset:
for i in range(1, 1 + int(input())):

  match_pattern = []

  for x in range(1, 32):
    for y in range(1, 32):
      for z in range(1, 32):

        if i == (x**2 + y ** 2 + z ** 2 + x * y + y * z + z * x):
          match_pattern.append([x, y, z])
  
  print(len(match_pattern))

### FIXED CODE ###

min, max, b = map(int, input().split())
result = 0
for i in range(min, max + 1):
  if i % b == 0:
    result += 1

print(result)
k, s = map(int, input_file[0].split())
count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if z >= 0 and z <= k:
            count+=1

print(count)


### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if z >= 0 and z <= k:
            count+=1

print(count)
print(int(input()[1:]))

### FIXED CODE ###

N=int(input())%1000

if N==0:
  print(0)
else:
  print(1000-N)
n = int(input())
travel = list(map(int,input().split()))
plan = travel.copy()
start = 0
answer = 0
answer_list = list()

for i in range(n):
    plan.pop(i)
    for j in range(len(plan)):
        answer += abs(plan[j]-start)
        start = plan[j]
    answer += abs(plan[len(plan)-1])
    answer_list.append(answer)
    answer = 0
    start = 0
    plan = travel.copy()
    
for i in range(len(answer_list)):
    print(answer_list[i])

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.insert(0,0)
a.insert(n+1,0)
total=0
#通常のコストを計算
for i in range(1,n+2):
    total+=abs(a[i]-a[i-1])
for i in range(1,n+1):
    ans=total-(abs(a[i]-a[i-1])+abs(a[i+1]-a[i]))+abs(a[i+1]-a[i-1])
    print(ans)
n,m=map(int,input().split())
MOD = 10**9+7
ans=1
def inv_mod(a, p=MOD):
    def inv_mod_sub(a, p):
        if a == 1:
            return 1, 0
        else:
            d, r = p//a, p%a
            x, y = inv_mod_sub(r, a)
            return y-d*x, x
    if p < 0: p = -p
    a %= p
    return inv_mod_sub(a,p)[0] % p

def comb_mod(n, k):
    if k < 0 or k > n:
        return 0
    else:
        return f_mod[n]*f_mod_inverse[k]*f_mod_inverse[n-k] % MOD
f_mod=[1]*(n+1)
f_mod_inverse=[1]*(n+1)
for i in range(1,n+1):
  f_mod[i]=f_mod[i-1]*i%MOD
  f_mod_inverse[i]=f_mod_inverse[i-1]*inv_mod(n)%MOD  
pf={}
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
for i in pf.values():
  ans*=comb_mod(i+n-1,n-1)
print(ans)

### FIXED CODE ###

import sys
n,m=map(int,input().split())
MOD = 10**9+7
ans=1
if m==1:
  print(1)
  sys.exit()
def inv_mod(a, p=MOD):
    def inv_mod_sub(a, p):
        if a == 1:
            return 1, 0
        else:
            d, r = p//a, p%a
            x, y = inv_mod_sub(r, a)
            return y-d*x, x
    if p < 0: p = -p
    a %= p
    return inv_mod_sub(a,p)[0] % p

def comb_mod(n, k):
    if k < 0 or k > n:
        return 0
    else:
        return f_mod[n]*f_mod_inverse[k]*f_mod_inverse[n-k] % MOD
pf={}
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
Max=max(list(pf.values()))
f_mod=[1]*(Max+n+1)
f_mod_inverse=[1]*(Max+n+1)
for i in range(1,Max+n+1):
  f_mod[i]=(f_mod[i-1]*i)%MOD
  f_mod_inverse[i]=(f_mod_inverse[i-1]*inv_mod(i)) % MOD  
for i in pf.values():
  ans*=comb_mod(i+n-1,n-1)
print(ans%MOD)
n, q = map(int, input().split())

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

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

def dfs(now, prev=-1):
    for next in g[now]:
        if next != prev:
            c[next] += c[now]
            dfs(next, now)

dfs(0)
print(*c)

### FIXED CODE ###

from collections import deque

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

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

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

q = deque([0])
flag = [False] * n
while q:
    v = q.pop()
    flag[v] = True
    for e in g[v]:
        if flag[e]:
            continue
        c[e] += c[v]
        q.append(e)

print(*c)
n=int(input())
a=list(map(int,input().split()))
o=[]
e=[]
for i in range(n):
  if i%2==0:
    o.append(a[i])
  else:
    e.append(a[i])
from collections import Counter as co
o=co(o)
e=co(e)
o['x']=0
e['x']=0
ov=o.values()+[0]
ev=e.values()+[0]
mo=max(ov)
me=max(ev)
if n==2:
  if a[0]==a[1]:
    print(1)
  else:
    print(0)
else:
  if max(o,key=o.get)==max(e,key=e.get):
    if mo>me:
      me=sorted(ev)[-2]
    else:
      mo=sorted(ov)[-2]
  print(n-mo-me)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
o=[]
e=[]
for i in range(n):
  if i%2==0:
    o.append(a[i])
  else:
    e.append(a[i])
from collections import Counter as co
o=co(o)
e=co(e)
o['x']=0
e['x']=0
ov=o.values()
ev=e.values()
mo=max(ov)
me=max(ev)
if n==2:
  if a[0]==a[1]:
    print(1)
  else:
    print(0)
else:
  if max(o,key=o.get)==max(e,key=e.get):
    if mo>me:
      me=sorted(ev)[-2]
    elif mo<me:
      mo=sorted(ov)[-2]
    else:
      mo=max(sorted(ev)[-2],sorted(ov)[-2])
  print(n-mo-me)
while True:
     a,b=map(int, input().split())
     x=[a,b]
     if a =0 and b=0:break
     x.sort()
     print(x[0],x[1])
     


### FIXED CODE ###

while True:
     a,b=map(int, input().split())
     x=[a,b]
     if a ==0 and b==0:break
     x.sort()
     print(x[0],x[1])
import itertools

l = input().split(' ')

n = int(l[0])
m = int(l[1])
d = int(l[2])

def get_beauty(l,d):
    # top = abs(l[0]-l[1])
    other = list(map(lambda x,y:abs(x-y),l[:-1],l[1:]))
    return other.count(d)

aa = [i+1 for i in range(n)]
candi = list(itertools.combinations_with_replacement(aa,r=m))
beauty = list(map(get_beauty,candi,[d for i in range(len(candi))]))
print(sum(beauty)/len(candi))


### FIXED CODE ###

l = input().split()
if int(l[0])+int(l[1])==15:
    print('+')
elif int(l[0])*int(l[1]) ==15:
    print('*')
else:
    print('x')
a, b =list(map(int,input().split())
print("{} {}".format(a*b,2*(a+b))



### FIXED CODE ###

a, b =list(map(int,input().split()))
print("{} {}".format(str(a*b),str(2*(a+b))))
N, K = map(int, input().split()) # 横に2個
A = list(map(int, input().split()))

A.sort(reverse=True)

dif = []
for i in range(N-1):
    dif.append(A[i] - A[i+1])
mind = min(dif)

ans = 'IMPOSSIBLE'
for a in A:
    if a < K:
        break
    if a == K:
        ans = 'POSSIBLE'
        break
    if (a-K) % mind == 0:
        ans = 'POSSIBLE'
        break

print(ans)

### FIXED CODE ###

N, K = map(int, input().split()) # 横に2個
A = list(map(int, input().split()))

A.sort(reverse=True)

dif = []
for i in range(N-1):
    d = A[i] - A[i+1]
    if d != 0:
        dif.append(d)
if dif:
    mind = min(dif)
else:
    mind = A[0]

ans = 'IMPOSSIBLE'
for a in A:
    if a < K:
        break
    if a == K:
        ans = 'POSSIBLE'
        break
    if (a-K) % mind == 0:
        ans = 'POSSIBLE'
        break

print(ans)
a, b, c, d = map(int, input().split())
ans = min(a, b) + min(c, d)
print(ans)

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())

print((a if a <= b else b) + (c if c <= d else d))
A=int(input())
B=int(input())
ans=(A-1)*(B-1)
print(ans)


### FIXED CODE ###

A,B=map(int,input().split())

ans=(A-1)*(B-1)
print(ans)
# coding: utf-8
import math

num, blue_num, red_num = map(int, input().split())
all_ball = blue_num + red_num
if blue_num == 0:
    print(0)
elif red_num == 0:
    print(num)
else:
    count = int(math.floor(num / all_ball))
    rest = int(num - (count * all_ball))
    if rest <= blue_num:
        blue_rest = rest
    print((count * blue_num)a + blue_rest)


### FIXED CODE ###

# coding: utf-8
import math

count = 0
num, blue_num, red_num = map(int, input().split())
all_ball = blue_num + red_num
count = num // all_ball
rest = num % all_ball
print(count * blue_num + min(rest, blue_num))
a,b=map(int,input().split())

if (ab%2==0):
    print('Even')

else:
    print('Odd')


### FIXED CODE ###

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

if (a*b%2==0):
    print('Even')

else:
    print('Odd')
N,K = list(map(int, input().split()))
D = set(input().split())

# シミュレーションでいける
for ans in range(N,10000):
    if all(d not in D for d in str(ans)):
        print(ans)
        exit()

raise AssertionError('バグってる')    

### FIXED CODE ###

N,K = list(map(int, input().split()))
D = set(input().split())

# シミュレーションでいける
for ans in range(N,100000):
    if all(d not in D for d in str(ans)):
        print(ans)
        exit()

raise AssertionError('バグってる')
s=input()
if s=="zyxwvutsrqponmlkjihgfedcba":print(-1);exit()
if len(s)!=26:
    print(s+sorted(list(set(list("zyxwvutsrqponmlkjihgfedcba"))-set(list(s))))[0])
else:
    des=set()
    l=list(s)
    while chr(ord(s[-1])+1) not in des:
        des.add(l.pop())
    print("".join(l[:-1])+sorted(list(des))[0])

### FIXED CODE ###

d="zyxwvutsrqponmlkjihgfedcba"
s=input()
if s=="zyxwvutsrqponmlkjihgfedcba":print(-1)
else:
    if len(s)!=26:
        for i in range(1,1+26):
            if d[-i] not in s:print(s+d[-i]);exit()
    else:
        from bisect import bisect_left as bl,bisect_right as br
        de=[s[-1]]
        for i in range(2,27):

            if de[-1]<s[-i]:de.append(s[-i])
            else:print(s[:-i]+de[bl(de,s[-i])]);exit()
a,b=map(int, raw_input().split())

if a>b:
 print 'a > b'
elif a<b:
 print 'a < b'
else a==b:
 print 'a == b'

### FIXED CODE ###

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

if a>b:
 print 'a > b'
elif a<b:
 print 'a < b'
else :
 print 'a == b'
import numpy as np

A, B, K = map(int,input().split())

C = np.arange(A,B+1)

if len(C)<=K:
    for x in range(len(C)):
        print(C[x])

        
elif len(C)<2*K:
    for y in range(K):
        print(C[y])
    for z in range(B-K-2,B-3):
        print(C[z])
        
        
else:
    for y in range(K):
        print(C[y])
    for z in range(B-K-2,B-2):
        print(C[z])


### FIXED CODE ###

A, B, K = map(int,input().split())

L = B - A + 1

if L >= 2*K:
    for i in range(A, A+K):
        print(i)
    for i in range(B-K+1,B+1):
        print(i)
        
else:
    for i in range(A,B+1):
        print(i)
import queue
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M = map(int, input().split())
X, Y = [0] * N, [0] * N
g = [[] for _ in range(N)]

for i in range(M):
    X[i], Y[i] = map(int, input().split())

    X[i] -= 1
    Y[i] -= 1
    g[X[i]].append(Y[i])
    g[Y[i]].append(X[i])


def bfs(x, y):
    visited = [False] * N
    q = queue.LifoQueue()
    for nx in g[x]:
        if nx == y:
            continue
        q.put(nx)

    visited[x] = True

    while not q.empty():
        cur = q.get()
        if cur == y:
            return True

        visited[cur] = True
        for nx in g[cur]:
            if visited[nx]:
                continue
            q.put(nx)

    return False

cnt = 0
for i in range(M):
    if not bfs(X[i], Y[i]):
        cnt += 1

print(cnt)

### FIXED CODE ###

import collections
import queue
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M = map(int, input().split())
X, Y = [0] * M, [0] * M
g = [[] for _ in range(N)]

for i in range(M):
    X[i], Y[i] = map(int, input().split())

    X[i] -= 1
    Y[i] -= 1
    g[X[i]].append(Y[i])
    g[Y[i]].append(X[i])


def bfs(x, y):
    visited = [False] * N
    q = queue.Queue()
    for nx in g[x]:
        if nx == y:
            continue
        q.put(nx)
        visited[nx] = True

    visited[x] = True

    while not q.empty():
        cur = q.get()
        if cur == y:
            return True

        for nx in g[cur]:
            if visited[nx]:
                continue
            q.put(nx)
            visited[nx] = True

    return False


cnt = 0
for i in range(M):
    if not bfs(X[i], Y[i]):
        cnt += 1

print(cnt)
from itertools import combinations

n = int(input())
D = []
ans = 0
for i in range(n):
    x,y = map(int,input().split())
    D.append((x,y))
for i,j in combinations(range(1,n+1),r=2):
    p,q = D[i-1]
    r,s = D[j-1]
    ans += ((p-r)**2+(q-s)**2)**(0.5)
print(2*ans/n)

### FIXED CODE ###

print(int(input())**2)
n = input()
A = list(map(int,input().split()))
ans = 1

for i in range(n):
	ans = ans*A[i]

print(ans)

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
ans = 1

if 0 in A:
  ans = 0
else:
  for i in range(n):
    ans = ans*A[i]
    if ans > 10**18:
        ans = -1
        break
 
print(ans)
S = input()
X, Y = map(int, input().split())

A = [0]
for s in S:
    if s == 'T':
        A.append(0)
    else:
        A[-1] += 1

B = [n for n in A[1:: 2]]
X -= A[0]
A = [n for n in A[2:: 2]]

def canGo(nums, g):
    if not nums:
        return g == 0

    bias = sum(nums)
    g += bias
    dp = (1 << bias)

    for n in nums:
        dp = (dp << n) | (dp >> n)
    return (dp & (1 << g)) > 0

if canGo(A, X) and canGo(B, Y):
    print('Yes')
else:
    print('No')


### FIXED CODE ###

S = input()
X, Y = map(int, input().split())

A = [0]
for s in S:
    if s == 'T':
        A.append(0)
    else:
        A[-1] += 1

B = [n for n in A[1:: 2]]
X -= A[0]
A = [n for n in A[2:: 2]]

def canGo(nums, g):
    if not nums:
        return g == 0

    bias = sum(nums) + 10
    g += bias
    if g < 0:
        return False

    dp = (1 << bias)

    for n in nums:
        dp = (dp << n) | (dp >> n)
    return (dp & (1 << g)) > 0

if canGo(A, X) and canGo(B, Y):
    print('Yes')
else:
    print('No')
H,W,N=map(int,input().split())
B=max(H,W)
ans=(N+B-1)//B
print(ans)

### FIXED CODE ###

H=int(input())
W=int(input())
N=int(input())
B=max(H,W)
ans=(N+B-1)//B
print(ans)
a,v = map(int, raw_input().split(' '))
b,w = map(int, raw_input().split(' '))
t = int(raw_input())

print 'YES' ig v*t >= w*t + abs(a-b) else 'NO'


### FIXED CODE ###

a,v = map(int, raw_input().split(' '))
b,w = map(int, raw_input().split(' '))
t = int(raw_input())

print 'YES' if (v*t >= w*t + abs(a-b)) else 'NO'
# その13
# A - Palindromic Number

N = int(input())

if N[0] = N[2]:
    print('Yes')
else:
    print('No')



### FIXED CODE ###

# その13
# A - Palindromic Number

N = str(input())

if N[0] == N[2]:
    print('Yes')
else:
    print('No')
N, K = map(int, input().split())
R = N - K
mod = 10 ** 9 + 7


def makeTableMod(N, mod=10 ** 9 + 7):
    fac = [1 for i in range(N)]
    finv = [1 for i in range(N)]
    inv = [1 for i in range(N)]
    for i in range(2, N):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv


fac, finv = makeTableMod(N-K+2, mod)


def binomialCoefficient(N, r, mod=10 ** 9 + 7):
    if N < r:
        return 0
    else:
        return fac[N] * (finv[r] * finv[N - r] % mod) % mod


def solve(i):
    # (N-K+1, i) * (K-1, i-1)を計算すれば良い
    ans = binomialCoefficient(N-K+1, i) * binomialCoefficient(K-1, i-1)
    return ans


for i in range(K):
    if i == 0:
        print((R+1) % mod)
    else:
        ans = solve(i+1)
        print(ans % mod)

### FIXED CODE ###

N, K = map(int, input().split())
R = N - K
mod = 10 ** 9 + 7


def makeTableMod(N, mod=10 ** 9 + 7):
    fac = [1 for i in range(N)]
    finv = [1 for i in range(N)]
    inv = [1 for i in range(N)]
    for i in range(2, N):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv


fac, finv = makeTableMod(2001, mod)


def binomialCoefficient(N, r, mod=10 ** 9 + 7):
    if N < r:
        return 0
    else:
        return fac[N] * (finv[r] * finv[N - r] % mod) % mod


def solve(i):
    # (N-K+1, i) * (K-1, i-1)を計算すれば良い
    ans = binomialCoefficient(N-K+1, i) * binomialCoefficient(K-1, i-1) % mod
    return ans


for i in range(K):
    if i == 0:
        print((R+1) % mod)
    else:
        ans = solve(i+1)
        print(ans % mod)
import itertools,math
n = int(input())
word = [input() for _ in range(n)]
count = 0

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for i in range(n):
    word[i] = sorted(word[i])

new_word = list(sorted(word))

x = 1

for i in range(n-1):
    if new_word[i] == new_word[i+1]:
        x += 1
    else:
        count += combinations_count(x,2)
        x = 1
if x >= 2:
    count +=  combinations_count(x,2)
    
print(count)

### FIXED CODE ###

import itertools,math
n = int(input())
word = [input() for _ in range(n)]
count = 0

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for i in range(n):
    word[i] = sorted(word[i])

new_word = list(sorted(word))

x = 1

for i in range(n-1):
    if new_word[i] == new_word[i+1]:
        x += 1
    elif x >= 2:
        count += combinations_count(x,2)
        x = 1
if x >= 2:
    count +=  combinations_count(x,2)

print(count)
# 16D8101022L 小林勇希 ID:k_mb python3

import math

cou = 0
n = int(input())
A = [int(input()) for i in range(n)]

for i in range(n):
    a_sq = int(math.sqrt(A[i]))
    for j in range(2,a_sq+2):
        if(A[i]%j==0 and not(A[i]==j)):
            break
        if(j==a_sq+1):
            cou += 1

print(cou)

"""実行結果

5
2
3
4
5
6
3



5
2
2
2
2
2
5

"""



### FIXED CODE ###

def insertion_sort(A,n):
    for i in range(n):
        v = A[i]
        j = i-1
        while(j>=0 and A[j]>v):
            A[j+1] = A[j]
            j = j-1
        A[j+1] = v
        for i in range(n-1):
            print(A[i],"",end="")
        print(A[n-1])

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

insertion_sort(A_idx,n)
n=int(input())
li=list(input())
t=n/2
if t%1:
  a=li[:t]
  b=li[:-t]
  for (i,j) in zip(a,b):
    if i==j:
    else:
      print('No')
      break
    print('Yes')
else:
  print('No')

### FIXED CODE ###

n=int(input())
li=list(input())
if n%2==0:
  t=int(n/2)
  a=li[:t]
  b=li[-t:]
  if a==b:
    print('Yes')
  else:
    print('No')
else:
  print('No')
import math

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


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


for i in range(1, k + 1):
    tmp1 = combinations_count(k - 1, k - (k - i + 1))
    tmp2 = combinations_count(n - k + 1, i)
    print((tmp1 * tmp2) % 1000000007)


### FIXED CODE ###

import math

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


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


for i in range(1, k + 1):
    if n - k + 1 >= i:
        tmp1 = combinations_count(k - 1, i - 1) % 1000000007
        tmp2 = combinations_count(n - k + 1, i) % 1000000007
        ans = (tmp1 * tmp2) % 1000000007
        print(ans)
    else:
        print(0)
import sys

n, a, b = map(int, sys.stdin.readline().split())

def main():
    d = b - a
    if d % 2 == 0:
        return d // 2
    else:
        return min(n - b, abs(1 - a)) + 1 + (d - 1) // 2)

if __name__ == '__main__':
    ans = main()
    print(ans)

### FIXED CODE ###

import sys

n, a, b = map(int, sys.stdin.readline().split())

def main(a, b):
    d = b - a
    if d % 2 == 0:
        return d // 2

    if n - b >= abs(1 - a):
        res = a
        b -= res
        a = 1
    else:
        res = n - b + 1
        a += res
        b = n

    res += (b - a) // 2
    return res

if __name__ == '__main__':
    ans = main(a, b)
    print(ans)
ABC = input().split()

if len(set(ABC)) == 2:
    print 'Yes'
else:
    print 'No'

### FIXED CODE ###

ABC = input().split()

if len(set(ABC)) == 2:
    print('Yes')
else:
    print('No')
import heapq
N,M=map(int, input().split())
A=list(map(int, input().split()))
for i in range(N):
    A[i]=-1*A[i]
heapq.heapify(A)
for i in range(M):
    q=heapq.heappop(A)
    q=q/2
    heapq.heappush(A,q)
ans=0
for i in range(N):
    ans+=-1*int(A[i])
print(ans)

### FIXED CODE ###

S=input()
if S=="Sunny":
    print("Cloudy")
elif S=="Cloudy":
    print("Rainy")
else:
    print("Sunny")
n,w=map(int,input().split())
wv=[[int(i) for i in input().split()]for _ in range(n)]

dp=[0]*(w+1)
dp[wv[0][0]]=wv[0][1]
for i in range(1,n):
    ww = wv[i][0]
    v = wv[i][1]
    for j in range(w,ww-1,-1):
        dp[j]=max(dp[j],dp[j-ww]+v)
print(max(dp))

### FIXED CODE ###

n,W=map(int,input().split())
wv=[[int(i) for i in input().split()]for _ in range(n)]
dp=[W+1]*(10**5+1)
dp[0]=0
for i in range(0,n):
    w,v = wv[i]
    for j in range(10**5,v-1,-1):
        dp[j]=min(dp[j],dp[j-v]+w)
for i in range(10**5,-1,-1):
    if dp[i]<=W:
        print(i)
        break
X = int(input())
'''
numの順番によっては買うことが出来ない金額が発生するためNG
num = [105, 104, 103, 102, 101, 100]

f = 0
for i in range(2**6):
    XX = X
    for j in range(6):
        if (i>>j)&1:
            XX %= num[j]
            if XX == 0:
                f = 1
print(f)
'''

num = [105, 104, 103, 102, 101, 100]

dp = [0 for _ in range(X)]
dp[0] = 1
f = 1

for i in range(X):
    for j in num:
        if i-j >= 0:
            if dp[i-j]:
                dp[i] = 1

for i in num:
    if not dp[X-i]:
        f = 0

print(f)

### FIXED CODE ###

X = int(input())
num = [105, 104, 103, 102, 101, 100]

dp = [0 for _ in range(X+1)]
dp[0] = 1
f = 1

for i in range(X+1):
    for j in num:
        if i-j >= 0:
            if dp[i-j]:
                dp[i] = 1

print(dp[X])
N, L = list(map(int, input().split()))

for i in range(1:N+1):
    apple_pie += L + i - 1

for k in range(1:N+1):
    ab = []
    ab += abs(L + k - 1)

if min(ab):
    print(apple_pie - (L + ab.index(min(ab))  - 1))

### FIXED CODE ###

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

apple_pie = 0
for i in range(1, N+1):
    apple_pie += L + i - 1

ab = []
for k in range(1, N+1):
    ab.append(abs(L + k - 1))

print(apple_pie - (L + ab.index(min(ab))  ))
n = int(input())
li = list(map(int, input().split()))

# print(li)
li.sort()
# print(li)

one = [1 for _ in range(n)]

if li[0] == li[1]:
    one[0] = 0

check = set([i for i in range(1, n)])

for i in range(n-1):
    a = set([_ for _ in range(i+1, n)]) & check
    # print(a)
    for j in a:
        if li[j] % li[i] == 0:
            one[j] = 0
            check.remove(j)
    check = set(list(check)[1:])
print(sum(one))


### FIXED CODE ###

n = int(input())
*A, = map(int, input().split())
maxA = max(A)
# C[a] = A内のaの個数
C = {a: 0 for a in A}
for a in A:
    C[a] += 1
# D[a]=1: Aにaより小さいaの約数が存在する
D = {a: 0 for a in A}
for a in A:
    if C[a] > 0:
        t = 2
        while a * t <= maxA:
            D[a * t] = 1
            t += 1
ans = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        ans += 1
print(ans)
n = int(input())
S = list(map(int,input().split())

a=soretd(S)
print(max(a)-min(a))


### FIXED CODE ###

n = int(input())
S = list(map(int, input().split()))
S = sorted(S)
print(S[-1] - S[0])
n,m = map(int,input().split())

h = list(map(int,input().split()))

root = [[] for i in range(n)]
for _ in range(n-1):
    a, b = (int(x) for x in input().split())
    root[b-1].append(a-1)
    root[a-1].append(b-1)

ans = 0

for i in range(n):
    flag = True
    for j in root[i]:
        if h[i] <= h[j]:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

### FIXED CODE ###

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

h = list(map(int,input().split()))

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

ans = 0

for i in range(n):
    flag = True
    if len(root[i]) > 0:
        for j in root[i]:
            if h[i] <= h[j]:
                flag = False
                break
    if flag:
        ans += 1
print(ans)