Harryxun/stf_run huggingface dataset:
max_num = 10**5+5
eratos_thenes_sieve = [0,0] + [1]*maxnum
n = 2 #素数
while n*n <= max_num:
  if eratos_thenes_sieve[n]:#
    for i in range(2*n, max_num, n):
      eratos_thenes_sieve[i] = 0
  n += 1
  
isLike2017 = [0] * max_num
cumulativeSums = [0]
for i in range(max_num):
  if eratos_thenes_sieve[i] and eratos_thenes_sieve[(i+1)//2]:
    isLike2017[i] = 1
  cumulativeSums.append(cumulativeSums[-1] + isLike2017[i])
  
  
q = int(input())

for i in range(q):
  l, r = map(int, input().split())
  print(cumulativeSums[r+1] - cumulativeSums[l])

### FIXED CODE ###

max_num = 10**5+5
eratos_thenes_sieve = [0,0] + [1]*max_num
n = 2 #素数
while n*n <= max_num:
  if eratos_thenes_sieve[n]:#
    for i in range(2*n, max_num, n):
      eratos_thenes_sieve[i] = 0
  n += 1
  
isLike2017 = [0] * max_num
cumulativeSums = [0]
for i in range(max_num):
  if eratos_thenes_sieve[i] and eratos_thenes_sieve[(i+1)//2]:
    isLike2017[i] = 1
  cumulativeSums.append(cumulativeSums[-1] + isLike2017[i])
  
  
q = int(input())

for i in range(q):
  l, r = map(int, input().split())
  print(cumulativeSums[r+1] - cumulativeSums[l])
s = input()
k = int(input())
flag = True

if len(s)==1:
    print(int(s))
    exit()

new = ''
for i in len(k):
    if s[i]!='1':
        flag = False
        new += i

if flag:
    print(1)
else:
    print(new[0])

### FIXED CODE ###

s = input()
k = int(input())
flag = False

for i in range(min(len(s), k)):
    if s[i] != '1':
        ans = int(s[i])
        flag = True
        break

if flag:
    print(ans)
else:
    print(1)
from sys import stdin
N,P=[int(x) for x in stdin.readline().rstrip().split()]
for i in reversed(range(int(pow(P,(1/N))))+1):
    tmp=i**N
    if P==1:
        ans=1
        break
    if N==1:
        ans=P
        break
    if P%tmp==0:
        ans=i
        break
print(ans)

### FIXED CODE ###

from sys import stdin
N=(stdin.readline().rstrip())
print(N.count("2"))
n,l=map(int,input().split())
a=[]
b=''
for k in range(n):
    a.append(input())
a.sort()
for i in range(l):
   b+=a[i]
print(b)

### FIXED CODE ###

n,l=map(int,input().split())
a=[]
b=''
for k in range(n):
    a.append(input())
a.sort()
for i in range(n):
   b+=a[i]
print(b)
N = int(input())
A = list(input().split())

A = sorted(A)
result = 1
max = 10**18
for a in A:
    result *= a
    if result > max:
        print(-1)
        break
    else:
        print(result)

### FIXED CODE ###

n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr) #配列を昇順ソートしておく(配列に0がある場合0が先頭に来るので、場合分けの必要がなくなる)
ans=1
for val in arr:
 ans*=val #Pythonは多倍長整数をサポートしているので単に積を求めれば十分
 if ans>10**18:
   print(-1)
   break
else:
 print(ans)
n = int(input())
a = sorted(list(map(int, input().split())),reverse=True)
mintot = sum(a)
cnt = 1
for i in range(n):
  tot -= a[i]
  if a[i] <= tot*2:
    break
  cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
a = sorted(list(map(int, input().split())),reverse=True)
tot = sum(a)
cnt = 1
for i in a:
  tot -= i
  if i > tot*2:
    break
  cnt += 1
print(cnt)
# -*- coding: utf-8 -*-
from itertools import product
from heapq import heappop, heappush
import numpy as np

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    for C in ((A,B), (B,A)):
        X = *filter(lambda c: int.__sub__(*c,)<0, zip(*C,)),
        dp = np.zeros((len(X), N+1), dtype=int)
        if X:
            dp[0] = X[0][1]*np.repeat(np.arange(N//X[0][0]+1), X[0][0])[:N+1]
            for i,w in product(range(1,len(X)), range(1,N+1)):
                dp[i][w] = (dp[i-1, w-X[i][0]*np.arange(w//X[i][0]+1)]+X[i][1]*np.arange(w//X[i][0]+1)).max()
            N = dp[-1][N]
    res = N

    return res

if __name__ == '__main__':
    print(solve())

### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import product
from heapq import heappop, heappush

def small_dp(N,A,B):
    *X, = filter(lambda c: int.__sub__(*c)<0, zip(A,B))
    k = len(X)
    if k == 0:
        return N
    if k == 1:
        return X[0][1]*(N//X[0][0]) + N%X[0][0]
    if k == 2:
        c = 0
        for i in range(N//X[0][0]+1):
            j = (N-i*X[0][0])//X[1][0]
            c = max(X[0][1]*i + X[1][1]*j + (N-i*X[0][0])%X[1][0], c)
        return c
    if k == 3:
        if (N//X[1][0]+1)*(N//X[0][0]+1) <= 10**6 :
            return max(X[0][1]*i + max(X[1][1]*j + X[2][1]*((N-i*X[0][0]-j*X[1][0])//X[2][0]) + ((N-i*X[0][0]-j*X[1][0])%X[2][0]) for j in range((N-i*X[0][0])//X[1][0]+1)) for i in range(N//X[0][0]+1))
        else:
            import numpy as np
            dp = np.zeros(N+1, dtype=int)
            for w in range(1,N+1):
                dp[w] = max(dp[w-X[i][0]]+X[i][1] if w>=X[i][0] else w for i in range(k))
            N = dp[-1]
            return N

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    res = small_dp(small_dp(N, A, B), B, A)

    return str(res)

if __name__ == '__main__':
    print(solve())
N, M = map(int, input().split())

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

C=[]
for i in range(M):
    c, d = map(int, input().split())
    C.append([c, d])

for i in range(N):
    saitei = float("inf")
    ans = 0
    for j in range(M):
    if abs(A[i][0]-B[j][0]) + abs(A[i][1]-B[j][1]) < saitei:
            saitei = abs(A[i][0]-B[j][0]) + abs(A[i][1]-B[j][1])
            ans = j+1   
    print(ans) 

### FIXED CODE ###

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

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

B=[]
for i in range(M):
    c, d = map(int, input().split())
    B.append([c, d])

for i in range(N):
    saitei = float("inf")
    ans = 0
    for j in range(M):
        if abs(A[i][0]-B[j][0]) + abs(A[i][1]-B[j][1]) < saitei:
            saitei = abs(A[i][0]-B[j][0]) + abs(A[i][1]-B[j][1])
            ans = j+1   
    print(ans)
#60b
a,b,c =map(int,input().split())
i=0
aa=a
while i<b:
    i+=1
    if aa%b == c:
        print('YES')
        exit()
    aa+=a
print('NO')

### FIXED CODE ###

#60a
a,b,c = input().split()
if a[-1]==b[0] and b[-1]==c[0]:
    print('YES')
else:
    print('NO')
for i in range(n):
    s = 'i'.lower()

print(s)


### FIXED CODE ###

N, K = (int(i) for i in input().split())
S = list(input())

S[K - 1] = S[K - 1].lower()
print(''.join(S))
N = int(input())

if N%2==0:
    print(1/2)
else:
    print((a+1)/a*2)


### FIXED CODE ###

N = int(input())

if N%2==0:
    print(1/2)
else:
    print((N+1)/(N*2))
n,k=map(int,input().split())
lists=list(map(int,input().split()))
GG=[]
for i in range(len(lists)+1):
    for j in range(i,len(lists)):
        
        G=sum(lists[i:j+1])
        GG.append(G)
        
GG=sorted(GG,reverse=True)      
maxi=format(GH[0],"b")
from collections import deque
d=deque()
e=deque()
for j in range(len(GG)):
    d.append(format(GG[j],"b").zfill(len(maxi)))
answer=0
index=0

while index!=len(maxi):
    counter=0
    for some in d:
        if some[index]=="1":
            counter+=1
            e.append(some)
    if counter>=k:
        answer+=2**(len(maxi)-1-index)
        d=e
        e=deque()
    elif counter<k:
        d=d
        e=deque()
        
    index+=1
    counter=0


print(answer)

### FIXED CODE ###

n,k=map(int,input().split())
lists=list(map(int,input().split()))
GG=[]
sumlist=[0]
a=0
for i in range(len(lists)):
    a+=lists[i]
    sumlist.append(a) 
for i in range(len(sumlist)):
    for j in range(i+1,len(sumlist)):
        
        G=sumlist[j]-sumlist[i]
        GG.append(G)
        
GG=sorted(GG,reverse=True)      
maxi=format(GG[0],"b")
from collections import deque
d=deque()
e=deque()
for j in range(len(GG)):
    d.append(format(GG[j],"b").zfill(len(maxi)))
answer=0
index=0
 
while index!=len(maxi):
    counter=0
    for some in d:
        if some[index]=="1":
            counter+=1
            e.append(some)
    if counter>=k:
        answer+=2**(len(maxi)-1-index)
        d=e
        e=deque()
    elif counter<k:
        d=d
        e=deque()
        
    index+=1
    counter=0
print(answer)
from scipy.special import comb

n, m = map(int, input().split())
print(comb(n, 2, exact=True)+comb(m,2, exact=True))

### FIXED CODE ###

from scipy.misc import comb

n, m = map(int, input().split())
print(comb(n, 2, exact=True)+comb(m,2, exact=True))
l,r = map(int, input().split())
if r-l+1>2019:
  print(0)
  exit()
L = []
for i in range(l,r-1):
  for j in range(i+1,r):
    a = i*j
    b = a%2019
    L.append(b)
print(min(L))


### FIXED CODE ###

l,r = map(int, input().split())
if r-l+1>2019:
  print(0)
  exit()
L = []
for i in range(l,r):
  for j in range(i+1,r+1):
    a = i*j
    b = a%2019
    L.append(b)
print(min(L))
#c
a, b = map(int ,input().split())
from math import gcd
print(a*b//gcd(a, b))

### FIXED CODE ###

#c
a, b = map(int ,input().split())
from fractions import gcd
print(a*b//gcd(a, b))
import sys
import copy
n=int(input())
maxmatch=n*(n-1)
a=[]
for i in range(n):
  b=list(map(int,input().split()))
  a.append(list(reversed(b)))
day=0
 
match=[0]*(n+1)
jyunban=[i for i in range(n)]
jyunban_n=[]
 
while match[n]<maxmatch:
  jyunban_n.clear()
  day+=1
  check=[True]*(n+1)
  for i in jyunban:
    if match[i]==n-1 or check[i]==False:
      continue
    else:
      vs=a[i][-1]-1
      if check[i] and check[vs]:
        if  a[i][-1]-1==vs and a[vs][-1]-1==i:
          a[i].pop(-1)
          a[vs].pop(-1)
          match[i]+=1
          match[vs]+=1
          match[n]+=2
          check[i]=False
          check[vs]=False
          check[n]=False
          jyunban_n.append(i)
          jyunban_n.append(vs)
      
    if i==jyunban[-1]:
      if check[n]:
        print(-1)
        sys.exit()
  jyunban=copy.copy(jyunban_n)
        
print(day)

### FIXED CODE ###

import sys
MAX_INT = int(10e9)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()
 
N = I()
a = [IL()[::-1] for i in range(N)]
 
used = [-1]*N
updatelist = [i for i in range(N)]
total = N*(N-1)//2
cnt = 0
days = 0
ul = []
while updatelist:
  ul = []
  for i in updatelist:
    #print(a)
    #print(i+1)
    if len(a[i]) > 0 and used[i] != days:
      numIND = a[i][-1] -1
      #print(numIND+1)
      if a[numIND][-1] == i+1 and used[numIND] != days:
        a[i].pop(-1)
        a[numIND].pop(-1)
        used[i] = days
        used[numIND] = days
        ul.append(i)
        ul.append(numIND)
        cnt += 1
  else:
    updatelist = ul[:]
    if len(ul) != 0:
      days += 1
#print(a)
#print(cnt)
if cnt == total:
  print(days)
else:
  print(-1)
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    int c = a * b;
    if (c % 2 == 0) cout << "Even" << endl;
    else cout << "Odd" << endl;
}

### FIXED CODE ###

a, b = map(int, input().split())
if a*b % 2 == 0:
    print("Even")
else:
    print("Odd")
numN = int(input())
args = input()

lines = list()


for i in range(numN):
    list.append(int(args[0:args.find(" ")]))

list_sorted = list.sorted
max_line = list_sorted[0]

for m in range(numN - 1)
    max_line = max_line - list_sorted[m+1]

if max_line < 0 :
    print(yes)
else
    print(no)

### FIXED CODE ###

numN = int(input())
args = input()
 
lines = list()
 
 
for i in range(numN):
    if i == numN - 1 :
        lines.append(int(args))
        break

    lines.append(int(args[0:args.find(" ")]))
    args = args[args.find(" ") + 1 :]
 
list_sorted = sorted(lines, reverse = True)
max_line = list_sorted[0]
 
for m in range(numN - 1):
    max_line = max_line - list_sorted[m+1]

if max_line < 0 :
    print('Yes')
else:
    print('No')
l=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

K=int(input())
print(l[K])


### FIXED CODE ###

l=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

K=int(input())
print(l[K-1])
n=int(input())
l=list(input().split())
m=0
for i in range(n):
  for j in range(i):
    if l[j]>l[i]:
      break
  else:
    m+=1
print(m)

### FIXED CODE ###

a, b=map(int, input().split())
if (a-1)>=b:
  print(a*2-1)
elif a==b or a==b:
  print(a+b)
else:
  print(b*2-1)
s, w = map(int, input().strip())
print(s)
print(w)
#if s > w:
#  print("safe")
#else:
#  print("unsafe")


### FIXED CODE ###

s, w = map(int, input().split())
if s > w:
  print("safe")
else:
  print("unsafe")
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

AA = list(reversed(A))
BB = list(reversed(B))

rest = K
ans = 0

def dfs(cost, aindex, bindex, score):

    if K == cost:
        # print("1:", score, cost)
        return score
    elif K < cost:
        # print("2:", score, cost)
        return score - 1
        # return -1
    
    if aindex == N and bindex == M:
        # print("3:", score, cost)
        return score

    if aindex >= N:
        return dfs(cost + B[bindex], aindex, bindex+1, score + 1)
    
    elif bindex >= M:
        return dfs(cost + A[aindex], aindex+1, bindex, score + 1)

    else:
        return max(dfs(cost + A[aindex], aindex+1, bindex, score + 1), dfs(cost + B[bindex], aindex, bindex + 1, score + 1))

print(max(dfs(A[0], 1, 0, 1), dfs(B[0], 0, 1, 1)))

### FIXED CODE ###

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

a, b = [0], [0]
for ai in A:
    a.append(a[-1] + ai)

for bi in B:
    b.append(b[-1] + bi)

# print(a, b)
ans = 0
bs = M
for i in range(N+1):
    if a[i] > K:
        break
    for j in reversed(range(bs+1)):
        if a[i] + b[j] <= K:
            ans = max(ans, i + j)
            bs = j
            break

print(ans)
input()
towers = list(map(int, input().split()))

ans = []
count = 0
for x in range(len(towers)-1):
  if towers[x] >= towers[x+1]:
    count+=1
  else:
    ans.append(count)
    count = 0
    
print(ans.max())

### FIXED CODE ###

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

max = 0
count = 0
for x in range(N-1):
  if H[x]>=H[x+1]:
    count += 1
  else:
    if max < count:
      max = count
    count=0
if max < count:
  max = count
print(max)
# coding: utf-8

from __future__ import print_function
from __future__ import unicode_literals
from __future__ import division
from __future__ import absolute_import

def array2d(row, col, init = None):
    return [[init for _ in range(col)] for _ in range(row)]

N, W = map(int, input().split(" "))
v = []
w = []
for i in range(N):
    vi, wi = map(int, input().split(" "))
    v.append(vi)
    w.append(wi)

dpt = array2d(N + 1, W + 1)

def dp(i, j):
    if dpt[i][j] is not None:
        return dpt[i][j]
    if i == 0:
        dpt[i][j] = 0
        return 0
    if j < w[i-1]:
        dpt[i][j] = dp(i-1, j)
        return dpt[i][j]
    dpt[i][j] = max(dp(i-1, j), dp(i, j-w[i-1]) + v[i-1])
    return dpt[i][j]

print(dp(N, W))

### FIXED CODE ###

# coding: utf-8
"""docstring"""


def arr2d(d1, d2, init=None):
    return [[init for i in range(d2)] for j in range(d1)]


def solve(N, W):
    v = [None] * N
    w = [None] * N
    for i in range(N):
        v[i], w[i] = map(int, input().split())

    # dp[i][j]: item 0..i ??????weight sum <= j ??¨????????????????????¶????????§????????§???value sum
    # (i: 0..N-1, j: 0..W)
    dp = arr2d(N, W + 1, 0)
    # i==0
    for j in range(0, W + 1):
        dp[0][j] = (j // w[0]) * v[0]
    for i in range(1, N):
        for j in range(0, W + 1):
            dp[i][j] = dp[i-1][j]
            if j >= w[i]:
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i])
                dp[i][j] = max(dp[i][j], dp[i][j-w[i]] + v[i])
    return dp[-1][-1]


def main():
    n, w = map(int, input().split())
    print(solve(n, w))


if __name__ == "__main__":
    main()
a,b=map(int,input().split())
c=0
if a!=3 and b!=3:
  c=3
elif a!=2 and b!=2:
  c=2
else:
  c=1

### FIXED CODE ###

a=int(input())
b=int(input())
if a!=3 and b!=3:
  print(3)
elif a!=2 and b!=2:
  print(2)
else:
  print(1)
a=input("a")
b=input("b")
i=int(a)-int(b)
c=input("c")
j=int(c)-int(i)
if j > 0:
    print(j)
else:
    print('0')


### FIXED CODE ###

A, B, C = map(int, input().split())
print(max(C - A + B, 0))
import itertools
num = int(input())
array1 = list(map(int, input().split()))
array2 = list(map(int, input().split()))
all_list = list(itertools.permutations(range(num)))

array1_index = all_list.index(array1) + 1
array2_index = all_list.index(array2) + 1

if array1 > array2:
  print(array1-array2)
else:
  print(array2-array1)

### FIXED CODE ###

import itertools
num = int(input())
array1 = tuple(map(int, input().split()))
array2 = tuple(map(int, input().split()))
all_list = list(itertools.permutations(range(1, num + 1)))
 
array1_index = all_list.index(array1) + 1
array2_index = all_list.index(array2) + 1
 
if array1_index > array2_index:
  print(array1_index-array2_index)
else:
  print(array2_index-array1_index)
n, k, c = map(int, input().split())
s = list(input())
cnt = s.count('o')
os = [i for i,x in enumerate(s) if x=='o']

from collections import deque

q = deque(os.copy())
_q1 = q.popleft()
m = k-1
l = [_q1]
while q and m > 0:
    _q2 = q.popleft()
    if _q2 - _q1 > c:
        l.append(_q2)
        _q1 = _q2
        m -= 1
        if m == 0:
            q = deque([])
    else:
        pass

q = deque(os.copy())
_q2 = q.pop()
m = k-1
r = [_q2]
while q and m > 0:
    _q1 = q.pop()
    if _q2 - _q1 > c:
        r.append(_q1)
        _q2 = _q1
        m -= 1
        if m == 0:
            q = deque([])
    else:
        pass

r = list(reversed(r))

# print(r)

ans = 0
for _l, _r in zip(l, r):
    if _l == _r:
        print(str(_l+1))
        ans = 1

if ans == 0:
    print()


### FIXED CODE ###

n, k, c = map(int, input().split())
s = list(input())
# cnt = s.count('o')
os = [i for i,x in enumerate(s) if x=='o']

from collections import deque

q = deque(os.copy())
_q1 = q.popleft()
m = k-1
l = [_q1]
if m > 0:
    while q:
        _q2 = q.popleft()
        if _q2 - _q1 > c:
            l.append(_q2)
            _q1 = _q2
            m -= 1
            if m == 0:
                q = deque([])
        else:
            pass

q = deque(os.copy())
_q2 = q.pop()
m = k-1
r = [_q2]
if m > 0:
    while q:
        _q1 = q.pop()
        if _q2 - _q1 > c:
            r.append(_q1)
            _q2 = _q1
            m -= 1
            if m == 0:
                q = deque([])
        else:
            pass

r = list(reversed(r))

ans = 0
for _l, _r in zip(l, r):
    if _l == _r:
        print(str(_l+1))
        ans = 1

if ans == 0:
    print()
N = int(input())
A = [int(x) for x in input().split()]
 
for i in N:
  if A[i]==0:
    print int(i)

### FIXED CODE ###

A = [int(x) for x in input().split()]
N = int(len(A))

for i in range(N):
  if A[i]-0==0:
    print(i+1)
cur = []

def recur(n):
    if n > 10 ** 9:
        return
    cur.append(n)
    for i in range(10):
        if abs(n % 10 - i) <= 1:
            recur(10 * n + i)

for i in range(1, 10):
    recur(i)
cur.sort()
n = int(input())
print((cur[n - 1]))

### FIXED CODE ###

cur = []

def recur(n):
    if n > 10 ** 10:
        return
    cur.append(n)
    for i in range(10):
        if abs(n % 10 - i) <= 1:
            recur(10 * n + i)

for i in range(1, 10):
    recur(i)
cur.sort()
n = int(input())
print((cur[n - 1]))
n, d = map(int, input().split())
ans = 0
for i in range(n):
    x, y = map(int, input().split())
    if x ** 2 + y ** 2 <= d ** 2
print(ans)

### FIXED CODE ###

n, d = map(int, input().split())
ans = 0
for i in range(n):
    x, y = map(int, input().split())
    if x ** 2 + y ** 2 <= d ** 2:
        ans += 1
print(ans)
N, K = map(int, input().split())

ok = [True]*10;

d = [int(s) for s in input().split()]

for i in d:
    ok[i] = False

ans = 0
for i in range(N, 10*N+1):
    j = i
    while j > 0 and ok[j%10]:
        j /= 10
    if j == 0:
        ans = i
        break

print(ans)


### FIXED CODE ###

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

ok = [True]*10

d = [int(s) for s in input().split()]

for i in d:
    ok[i] = False

ans = 0
for i in range(N, 10*N+1):
    j = i
    while j > 0 and ok[j%10]:
        j //= 10
    if j == 0:
        ans = i
        break

print(ans)
# 再帰関数使用時は再帰上限を十分にとること
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
 
# グローバル変数定義
INF = 10 ** 13
N, W = map(int, input().split())
 
# knopsock[n][0] = w    :   n = 品物の位置 , w = 重さ
# knopsock[n][1] = v    :   n = 品物の位置 , v = 価値
knapsack = [list(map(int, input().split())) for _ in range(N)]
 
# db[n][w] = v          :   w = 現在の重さ, n = 見てきた品物の数, v = 現在の価値
db = [[INF] * W for _ in range(N)]
 
 
def dfs(n, w):
    """
    品物に対する深さ優先探索による全探索（メモ化再帰）。
 
    Args:
        n (int) : 見てきた品物の数
        w (int) : ここまでの重さの総和
 
    Returns:
        v (int) : 価値の総和の最大値
    """
 
    # 終了条件：現在の個数が全ての品物の個数を越える
    if n >= N:
        return 0
 
    if w + knapsack[n][0] > W:
        # １つ前までの重さ + 今回の品物の重さが重さの最大値を越えていたら今回の品物は選べない
        return dfs(n + 1, w)
    else:
        # 今回の品物を選ぶか選ばないかで全探索
        return max([dfs(n + 1, w), dfs(n + 1, w + knapsack[n][0]) + knapsack[n][1]])
 
 
def main():
    out = dfs(0, 0)
    print(out)
 
 
if __name__ == "__main__":
    main()
# 再帰関数使用時は再帰上限を十分にとること
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

# グローバル変数定義
INF = 10 ** 13
N, W = map(int, input().split())

# knopsock[n][0] = w    :   n = 品物の位置 , w = 重さ
# knopsock[n][1] = v    :   n = 品物の位置 , v = 価値
knapsack = [list(map(int, input().split())) for _ in range(N)]

# db[n][w] = v          :   w = 現在の重さ, n = 見てきた品物の数, v = 現在の価値
db = [[INF] * W for _ in range(N)]


def dfs(n, w):
    """
    品物に対する深さ優先探索による全探索（メモ化再帰）。

    Args:
        n (int) : 見てきた品物の数
        w (int) : ここまでの重さの総和

    Returns:
        v (int) : 価値の総和の最大値
    """

    # 終了条件：現在の個数が全ての品物の個数を越える
    if n >= N:
        return 0

    if w + knapsack[n][0] > W:
        # １つ前までの重さ + 今回の品物の重さが重さの最大値を越えていたら今回の品物は選べない
        return dfs(n + 1, w)
    else:
        # 今回の品物を選ぶか選ばないかで全探索
        return max([dfs(n + 1, w), dfs(n + 1, w + knapsack[n][0]) + knapsack[n][1]])


def main():
    out = dfs(0, 0)
    print(out)


if __name__ == "__main__":
    main()
提出情報
提出日時	2019-11-17 17:37:04
問題	

### FIXED CODE ###

import sys
readline = sys.stdin.readline


def chmax(a, b):
    """
    2値の大きい値を返す

    Args:
        a   (int)   : 値１
        b   (int)   : 値２
    Return:
        a   (int)   : aまたはbの大きい値
    """
    if a < b:
        a = b
    return a


def main():

    N, W = map(int, readline().split())

    # knopsock[n][0] = w    :   n = 品物の位置 , w = 重さ
    # knopsock[n][1] = v    :   n = 品物の位置 , v = 価値
    knapsack = [list(map(int, readline().split())) for _ in range(N)]

    # db[n][w] = v          :   w = 現在の重さ, n = 見てきた品物の数, v = 現在の価値
    dp = [[0] * (W + 1) for _ in range(N + 1)]

    for n in range(1, N + 1):
        for w in range(W + 1):
            if w - knapsack[n - 1][0] < 0:
                dp[n][w] = dp[n - 1][w]
            else:
                dp[n][w] = chmax(dp[n - 1][w], dp[n - 1]
                                 [w - knapsack[n - 1][0]] + knapsack[n - 1][1])

    print(dp[N][W])


if __name__ == "__main__":
    main()
# coding: utf-8

X = int(input())
flg = 0
for A in range(-100, 100):
    for B in range(-80, 80):
        if A ** 5 - B ** 5 == X:
            print(f"{A} {B}")
            flg = 1
            break
    if flg:
        break


### FIXED CODE ###

# coding: utf-8

S = input()
arc = "ARC"
abc = "ABC"
if S == arc:
    print(abc)
elif S == abc:
    print(arc)