Problem:


上司のおごり

会津太郎さんの会社には、割り切れない事が大嫌いな上司がいます。太郎さんがその上司と食事に行くときは、割り勘で会計をしているのですが、支払金額が参加人数で割り切れないときは、いつも上司がおごってくれています。

 ある日、太郎さんは食事会の幹事になりました。お金の少ない太郎さんは、その上司を誘ってなんとかおごってもらえるように出来ないか考えました。もう料理屋に注文をしなければならないのですが、まだ何人参加するかは分からないので、どんな人数が参加してもおごってもらえるような注文をしておきたいようです。太郎さんの同期で、同じく食事会に参加する予定のあなたは、太郎さんに協力して、予算額以下で最大のどんな人数でも割り切れない金額を算出することにしました。

 料理の種類、各料理の料金、予算額を入力とし、予算額以下で最大のどんな数字でも割り切れない合計金額(ただし、 1 と合計金額は除く)を出力するプログラムを作成してください。なお、各種類の料理は複数個注文できますが、全種類の料理を注文する必要はありません。ただし、このような合計金額がない場合は、 NA と出力してください。

Input

複数のデータセットの並びが入力として与えられます。  入力の終わりはゼロふたつの行で示されます。
各データセットは以下の形式で与えられます。

n x
v1
v2
:
vn

1 行目に料理の種類 n (1 ≤ n ≤ 30) と予算額 x (1 ≤ x ≤ 1000000) が空白区切りで与えられます。続くn 行に i 種類目の料理の金額を表す整数 vi (1 ≤ vi ≤ 1000000) が与えられます。

データセットの数は 100 を超えません。

Output

入力データセットごとに、予算額に最も近い合計金額、または NA を１行に出力します。

Sample Input

4 15000
305
260
129
500
3 400
10
20
30
3 200909
5
9
12
0 0

Output for the Sample Input

14983
NA
200909



Sample input:
4 15000
305
260
129
500
3 400
10
20
30
3 200909
5
9
12
0 0


Sample output:
14983
NA
200909

Submission status: Accepted

Solution code:

def solve(price, ps, is_prime):
    dp = [0] * ((price >> 5) + 1)
    for i in range(0, price + 1,ps[0]):
        dp[i >> 5] |= 1 << (i & 31)
    dp[0] = 1
    for i in range(1, len(ps)):
        cur_p = ps[i]
        r = cur_p & 31
        rest = 0
        if cur_p >= 32:
            for p in range(cur_p, price + 1, 32):
                i1 = (p - cur_p) >> 5
                i2 = p >> 5
                v = dp[i1]
                dp[i2] |= ((v << r)&(2**33-1)) | rest
                rest = (v >> (32 - r)) & ((1 << r) - 1)
        else:
            for p in range(cur_p, price + 1):
                dp[p >> 5] |= (dp[(p - cur_p) >> 5] >> ((p - cur_p) & 31) & 1) << (p & 31)

    p = -1
    for i in range(price+1, 0,-1):
        if is_prime[i] and (dp[i >> 5] >> (i & 31) & 1):
            p = i
            break
    if p == -1:
        print("NA")
    else:
        print(p)
     
def main():
    N = 1000001
    temp = [True]*(N+1)
    temp[0] = temp[1] = False
    for i in range(2, int((N+1)**0.5)+1):
        if temp[i]:
            temp[i+i::i] = [False]*(len(temp[i+i::i]))

    while True:
        n, price = map(int,input().split())
        if n == 0 and price == 0:
            return
        ps = []
        for i in range(n):
            ps.append(int(input()))
        solve(price, ps, temp)
 
main()

Submission status: Runtime Error

Solution code:
def main():
  tf = [True] * 1000001
  tf[0] = tf[1] = False
  for i in range(2, 1001):
    if tf[i]:
      for j in range(i ** 2 , 1000001, i):
        tf[j] = False
  
  while True:
    n, x = map(int, input().split())
    if n == 0:
      break
    can = [False] * (x + 1)
    can[0] = True
    for _ in range(n):
      v = int(input())
      for i in range(x - v + 1):
        if can[i]: can[i + v] = True
    for i in range(x, -1, -1):
      if can[i] and tf[i]:
        print(i)
        break
    else:
      print("NA")
main()

Submission status: Runtime Error

Solution code:
def main():
  tf = [True] * 1000001
  tf[0] = tf[1] = False
  for i in range(2, 1001):
    if tf[i]:
      for j in range(i ** 2 , 1000001, i):
        tf[j] = False
  primes = [i for i in range(1000001) if tf[i]]
  
  while True:
    n, x = map(int, input().split())
    if n == 0:
      break
    can = [False] * (x + 1)
    can[0] = True
    for _ in range(n):
      v = int(input())
      for i in range(x - v + 1):
        if can[i]: can[i + v] = True
    can_nums = [i for i in range(x, -1, -1) if can[i]]
    for num in can_nums:
      if num in primes:
        print(num)
        break
    else:
      print("NA")
   
main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_left as bl
def main():
  tf = [True] * 1000004
  tf[0] = tf[1] = False
  for i in range(2, 1001):
    if tf[i]:
      for j in range(i ** 2 , 1000004, i):
        tf[j] = False
  primes = [i for i in range(1000004) if tf[i]]
  
  while True:
    n, x = map(int, input().split())
    if n == 0:
      break
    can = [False] * (x + 1)
    can[0] = True
    for _ in range(n):
      v = int(input())
      for i in range(x - v + 1):
        if can[i] and not can[i + v]: can[i + v] = True
    can_nums = [i for i in range(x, -1, -1) if can[i]]
    for num in can_nums:
      if primes[bl(primes, num)] == num:
        print(num)
        break
    else:
      print("NA")
   
main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_left as bl
def main():
  tf = [True] * 1000004
  tf[0] = tf[1] = False
  for i in range(2, 1001):
    if tf[i]:
      for j in range(i ** 2 , 1000004, i):
        tf[j] = False
  primes = [i for i in range(1000004) if tf[i]]
  
  while True:
    n, x = map(int, input().split())
    if n == 0:
      break
    can = [False] * (x + 1)
    can[0] = True
    for _ in range(n):
      v = int(input())
      for i in range(x - v + 1):
        can[i + v] = can[i] or can[i + v]
    for i in range(x, -1, -1):
      if tf[i] and can[i]:
        print(i)
        break
    else:
      print("NA")
  
main()

Submission status: Runtime Error

Solution code:
def sieve():
    n = 10000001
    p = [1] * n
    p[0] = p[1] = 0
    
    for i in range(int(n ** 0.5)):
        if p[i]:
            for j in range(2 * i, len(p), i):
                p[j] = 0
    return p

def solve(p, menu, x):
    menu.sort()
    
    num = [0] * (x + 1)
    for i in range(0,len(num),menu[0]):
        num[i] = 1
    for mi in menu[1:]:
        for i in range(mi, len(num)):
            if num[i - mi]:
                num[i] = i
    for i in reversed(range(1, len(num))):
        if p[i] and num[i]:
            return i
    return 'NA'

import sys
f = sys.stdin



p = sieve()
while True:
    n, x = map(int, f.readline().split())
    if n == 0:
        break
    menu = [int(f.readline()) for _ in range(n)]
    print(solve(p, menu, x))

Submission status: Runtime Error

Solution code:
def sieve():
    n = 1000001
    p = [1] * n
    p[0] = p[1] = 0
    
    for i in range(int(n ** 0.5)):
        if p[i]:
            for j in range(2 * i, len(p), i):
                p[j] = 0
    return p

def solve(p, menu, x):
    menu.sort()
    
    num = [0] * (x + 1)
    for i in range(0,len(num),menu[0]):
        num[i] = 1
    for mi in menu[1:]:
        for i in range(mi, len(num)):
            if num[i - mi]:
                num[i] = i
    for i in reversed(range(1, len(num))):
        if p[i] and num[i]:
            return i
    return 'NA'

import sys
f = sys.stdin


p = sieve()
while True:
    n, x = map(int, f.readline().split())
    if n == 0:
        break
    menu = [int(f.readline()) for _ in range(n)]
    print(solve(p, menu, x))

Submission status: Runtime Error

Solution code:
def sieve():
    n = 1000001
    p = [1] * n
    p[0] = p[1] = 0
    
    for i in range(int(n ** 0.5)):
        if p[i]:
            for j in range(2 * i, len(p), i):
                p[j] = 0
    return p

def solve(p, menu, x):
    menu.sort(reverse=True)
    
    num = [0] * (x + 1)
    for i in range(0,len(num),menu[-1]):
        num[i] = 1
    for mi in menu[:-1]:
        for i in range(len(num) - mi):
            if num[i]:
                num[i + mi] = 1
                
    for i in reversed(range(1, len(num))):
        if p[i] and num[i]:
            return i
    return 'NA'

import sys
f = sys.stdin

p = sieve()
while True:
    n, x = map(int, f.readline().split())
    if n == 0:
        break
    menu = [int(f.readline()) for _ in range(n)]
    print(solve(p, menu, x))

Submission status: Runtime Error

Solution code:
def sieve():
    p = [1] * 1000001
    p[0] = p[1] = 0
    
    for i in range(1000):
        if p[i]:
            for j in range(i * i, 1000001, i):
                p[j] = 0
    return p

def solve(p, menu, x):
    menu.sort()
    
    num = [0] * (x + 1)
    for i in range(0,len(num),menu[0]):
        num[i] = 1
    for mi in menu[1:]:
        for i in range(len(num) - mi):
            if num[i] and not num[i + mi]:
                num[i + mi] = 1
                
    for i in reversed(range(1, len(num))):
        if p[i] and num[i]:
            return i
    return 'NA'

import sys
f = sys.stdin

p = sieve()
while True:
    n, x = map(int, f.readline().split())
    if n == 0:
        break
    menu = [int(f.readline()) for _ in range(n)]
    print(solve(p, menu, x))

Submission status: Runtime Error

Solution code:
def sieve():
    p = [1] * 1000001
    p[0] = p[1] = 0
    
    for i in range(1000):
        if p[i]:
            for j in range(i * i, 1000001, i):
                p[j] = 0
    return p

def solve(p, menu, x):
    menu.sort()
    
    num = [0] * (x + 1)
    num[0] = 1
    
    for mi in menu:
        for i in range(len(num) - mi):
            if num[i]:
                pass                
    for i in reversed(range(1, len(num))):
        if p[i] and num[i]:
            return i
    return 'NA'

import sys
f = sys.stdin

p = sieve()
while True:
    
    n, x = map(int, f.readline().split())
    if n == 0:
        break
    menu = [int(f.readline()) for _ in range(n)]
    print(solve(p, menu, x))

Submission status: Runtime Error

Solution code:
def sieve():
    p = [1] * 1000001;p[0] = p[1] = 0
    
    for i in range(1000):
        if p[i]:
            for j in range(i * i, 1000001, i):p[j] = 0
    return p

def solve(p, menu, x):
    menu.sort()
    
    num = [0] * (max(menu) + x + 1);num[0] = 1 
    
    for i in range(x + 1):
        for mi in menu:
            if num[i - mi]:
                num[i] = 1
                break
    for i in reversed(range(1, x + 1)):
        if p[i] and num[i]:
            return i
    return 'NA'
import sys
f = sys.stdin

p = sieve()
while True:
    
    n, x = map(int, f.readline().split())
    if n == 0:
        break
    menu = [int(f.readline()) for _ in range(n)]
    print(solve(p, menu, x))

Submission status: Runtime Error

Solution code:
def sieve():
    p = [1] * 1000001;p[0] = p[1] = 0
    
    for i in range(1000):
        if p[i]:
            for j in range(i * i, 1000001, i):p[j] = 0
    return p

def solve(p, menu, x):
    menu.sort()
    
    num = [0] * (x + 1)
    num[0] = 1
    
    for mi in menu:
        if num[mi]:
            continue
        for i in range(len(num) - mi):
            if num[i] and not num[i + mi]:
                num[i + mi] = 1
                
    for i in reversed(range(1, len(num))):
        if p[i] and num[i]:
            return i
    return 'NA'

import sys
f = sys.stdin

p = sieve()
while True:
    
    n, x = map(int, f.readline().split())
    if n == 0:
        break
    menu = [int(f.readline()) for _ in range(n)]
    print(solve(p, menu, x))

Submission status: Runtime Error

Solution code:
def sieve():
    p = [1] * 1000001;p[0] = p[1] = 0
    
    for i in range(1000):
        if p[i]:
            for j in range(i * i, 1000001, i):p[j] = 0
    return p

def solve(p, menu, x):
    menu.sort()
    num = [0] * (max(menu) + x + 1);num[0] = 1 
    
    cnt = 0
    for i in range(x + 1):
        if p[i]:
            cnt += 2 * len(menu)
            for mi in menu:num[i + mi] = 1
            if i < cnt:break
    for j in range(i,x + 1):
        for mj in menu:
            if num[j - mj]:
                num[j] = 1
                break
                
                
                
    for i in reversed(range(1, x + 1)):
        if p[i] and num[i]:
            return i
    return 'NA'

import sys
f = sys.stdin

p = sieve()
while True:
    
    n, x = map(int, f.readline().split())
    if n == 0:
        break
    menu = [int(f.readline()) for _ in range(n)]
    print(solve(p, menu, x))

Submission status: Runtime Error

Solution code:
from sys import stdin
readline = stdin.readline


import math
def sieve(n):
    p = [1] * (n + 1)
    p[0] = p[1] = 0
    
    for i in range(math.ceil((n + 1) ** 0.5)):
        if p[i]:
            for j in range(2 * i, len(p), i):
                p[j] = 0
    return p

prime = sieve(1000000)

def solve(price, x):
    dp = [0] * (x + 1)
    dp[0] = 1

    price.sort()
    for pi in price:
        for i in range(pi, len(dp)):
            if dp[i - pi]:dp[i] = 1
    for i in reversed(range(2, len(dp))):
        if dp[i] and prime[i]:return i
    return None

def main():
    while True:
        n, x = map(int, readline().split())
        if n == 0:
            break
        price = [int(readline()) for _ in range(n)]
        amount = solve(price, x)
        print(amount if amount else 'NA')
main()

Submission status: Runtime Error

Solution code:
from sys import stdin
readline = stdin.readline


import math
def sieve(n):
    p = [1] * (n + 1)
    p[0] = p[1] = 0
    
    for i in range(math.ceil((n + 1) ** 0.5)):
        if p[i]:
            for j in range(2 * i, len(p), i):
                p[j] = 0
    return p

prime = sieve(1000000)

def solve(price, x):
    dp = [0] * (x + 1)
    dp[0] = 1

    price.sort()
    for pi in price:
        for i in range(0, len(dp), pi):
            dp[i] = 1
    for pi in price:
        for i in range(pi, len(dp)):
            if not dp[i] and dp[i - pi]:
                dp[i] = 1
    for i in reversed(range(2, len(dp))):
        if dp[i] and prime[i]:
            return i
    return None

def main():
    while True:
        n, x = map(int, readline().split())
        if n == 0:
            break
        price = [int(readline()) for _ in range(n)]
        amount = solve(price, x)
        print(amount if amount else 'NA')
main()

Submission status: Runtime Error

Solution code:
from sys import stdin
readline = stdin.readline


import math
def sieve(n):
    p = [1] * (n + 1)
    p[0] = p[1] = 0
    
    for i in range(math.ceil((n + 1) ** 0.5)):
        if p[i]:
            for j in range(2 * i, len(p), i):
                p[j] = 0
    return p

prime = sieve(1000000)

def solve(price, x):
    dp = [0] * (x + 1)
    dp[0] = 1

    price.sort()
    for pi in price:
        for i in range(0, len(dp), pi):
            dp[i] = 1
    for pi in price[1:]:
        for i in range(pi, len(dp)):
            if not dp[i] and dp[i - pi]:
                dp[i] = 1
    for i in reversed(range(2, len(dp))):
        if dp[i] and prime[i]:
            return i
    return None

def main():
    while True:
        n, x = map(int, readline().split())
        if n == 0:
            break
        price = [int(readline()) for _ in range(n)]
        amount = solve(price, x)
        print(amount if amount else 'NA')
main()

Submission status: Runtime Error

Solution code:
from sys import stdin
readline = stdin.readline


import math
def sieve(n):
    p = [1] * (n + 1)
    p[0] = p[1] = 0
    
    for i in range(math.ceil((n + 1) ** 0.5)):
        if p[i]:
            for j in range(2 * i, len(p), i):
                p[j] = 0
    return p

prime = sieve(1000000)


def solve(price, x):
    dp = [0] * (x + 1)
    dp[0] = 1

    price.sort()

    for i in reversed(range(1, len(price))):
        for j in range(i):
            if price[i] % price[j] == 0:
                del price[i]
                break

    for pi in price:
        for i in range(0, len(dp), pi):
            dp[i] = 1
    for pi in price[1:]:
        for i in range(pi, len(dp)):
            if not dp[i] and dp[i - pi]:
                dp[i] = 1
    for i in reversed(range(2, len(dp))):
        if dp[i] and prime[i]:
            return i
    return None

def main():
    while True:
        n, x = map(int, readline().split())
        if n == 0:
            break
        price = [int(readline()) for _ in range(n)]
        amount = solve(price, x)
        print(amount if amount else 'NA')
main()

Submission status: Runtime Error

Solution code:
while True:
    n, x = map(int, raw_input().split())
    if n == x == 0: break
    p, ls = [1] * x, [0]*x
    p[0] = p[1] = 0 
    ls[0] = 1
    m, s = [], 0
    for i in range(2, int(x**0.5)+1):
        if p[i]:
            for j in range(i*2, x, i):
                p[j] = 0
    for i in range(n):
        m.append(input())
    for i in range(x):
        if ls[i] == 1:
            for j in m:
                if i+j < x:
                    ls[i+j] = 1
    for i in range(x)[:0:-1]:
        if p[i] == ls[i] == 1:
            print i
            break
    else: print 'NA'

Submission status: Runtime Error

Solution code:
while True:
    n, x = map(int, raw_input().split())
    if n == x == 0: break
    x += 1
    p, ls, m = [1] * x, [0]*x, []
    p[0] = p[1] = 0 
    ls[0] = 1
    for i in range(2, int(x**0.5)+1):
        if p[i]:
            for j in range(i*2, x, i):
                p[j] = 0
    for i in range(n):
        m.append(input())
    for i in range(x):
        if ls[i] == 1:
            for j in m:
                if i+j < x:
                    ls[i+j] = 1
    for i in range(x)[:0:-1]:
        if p[i] == ls[i] == 1:
            print i
            break
    else: print 'NA'

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import math

#must import library 'math'
def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):
        if serial >= sqrt:
            return input_list
        for s in range(serial ** 2, num, serial): 
            input_list[s] = False

primeTable = sieve_of_erastosthenes((10**6))

while True:
    n,x = map(int,raw_input().split())
    if n == 0 and x == 0:
        break
    dishes = []
    dp = [False for i in range(x+1)]
    dp[0] = True
    for i in range(n):
        dishes.append(int(raw_input()))

    ans = 'NA'
    for dish in dishes:
        for i in range(0,x+1):
            if (i + dish < x+1) and dp[i] is not False:
                if primeTable[i+dish] is True:
                    ans = i+dish
                dp[i + dish] = True
    print(ans)

Submission status: Runtime Error

Solution code:
from math import sqrt
prime = [1 for _ in xrange(10**6+1)]
prime[1] = 0
prime[0] = 0
for i in xrange(2, int(sqrt(10**6+1))+1):
    if prime[i] == 1:
        for j in xrange(i+i, 10**6+1, i):
            prime[j] = 0
while True:
    N, X = map(int, raw_input().split())
    if (N, X) == (0, 0): break
    price = [input() for _ in xrange(N)]
    dp = [0] * (X+1)
    dp[0] = 1
    for i in xrange(X+1):
        if dp[i] == 0: continue
        for p in price:
            if i + p <= X:
                dp[i+p] = 1
    for i in range(X, -1, -1):
        if dp[i] == 1 and prime[i] == 1:
            print(i)
            break
    else:
        print("NA")

Submission status: Runtime Error

Solution code:
from math import sqrt
prime = [1 for _ in xrange(10**6+1)]
prime[1] = 0
prime[0] = 0
for i in xrange(2, int(sqrt(10**6+1))+1):
    if prime[i] == 1:
        for j in xrange(i+i, 10**6+1, i):
            prime[j] = 0
while True:
    N, X = map(int, raw_input().split())
    if (N, X) == (0, 0): break
    price = [input() for _ in xrange(N)]
    dp = [0] * (X+1)
    dp[0] = 1
    for i in xrange(X+1):
        if dp[i] == 0: continue
        for p in price:
            if i + p <= X:
                dp[i+p] = 1
    for i in xrange(X, -1, -1):
        if dp[i] == 1 and prime[i] == 1:
            print(i)
            break
    else:
        print("NA")

Submission status: Runtime Error

Solution code:
from math import sqrt
prime = [1 for _ in xrange(10**6+1)]
prime[1] = 0
prime[0] = 0
for i in xrange(2, int(sqrt(10**6+1))+1):
    if prime[i] == 1:
        for j in xrange(i+i, 10**6+1, i):
            prime[j] = 0
while True:
    N, X = map(int, raw_input().split())
    if (N, X) == (0, 0): break
    price = [input() for _ in xrange(N)]
    dp = [0] * (X+1)
    dp[0] = 1
    for i in xrange(X+1):
        if dp[i] == 0: continue
        for p in price:
            if i + p <= X:
                dp[i+p] = 1
    for i in xrange(X, -1, -1):
        if i > 0 and dp[i] == 1 and prime[i] == 1:
            print(i)
            break
    else:
        print("NA")

Submission status: Runtime Error

Solution code:
from math import sqrt
class Prime:
    """ make prime numbers lists """

    def __init__(self, n):
        self.is_prime = [True for _ in range(n+1)]
        self.primeList = []
        self.is_prime[0] = False
        self.is_prime[1] = False
        for i in range(2, int(pow(n, 0.5))+1):
            if self.is_prime[i] == True:
                self.primeList.append(i)
                for j in range(2*i, n+1, i):
                    self.is_prime[j] = False

    def isPrime(self, n):
        return self.is_prime[n]

    def nthPrime(self, n):
        return self.primeList[n-1]

prime = Prime(10**6)
while True:
    N, X = map(int, input().split())
    if (N, X) == (0, 0): break
    price = [int(input()) for _ in range(N)]
    dp = [0] * (X+1)
    dp[0] = 1
    for i in range(X+1):
        if dp[i] == 0: continue
        for p in price:
            if i + p <= X:
                dp[i+p] = 1
    for i in range(X, -1, -1):
        if dp[i] == 1 and prime.isPrime(i) == 1:
            print(i)
            break
    else:
        print('NA')

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import pdb
import sys,math,time

#Debug=True
Debug=False
nmax=1000000
#unit_cost = [500,305,260,129]
#total_cost = 15000
#unit_cost = [12,9,5]
#total_cost = 200909
unit_cost = []
total_cost=0
primes=[]
pmax=-1

def ip(f,g):
    s=0
    for i in zip(f,g):
        s += i[0]*i[1]
    return(s)
            
def prime():
    fl = [True for _ in range(nmax+1)]
    yield 2
    yield 3
    k=5
    while k < nmax:
        if fl[k]:
            yield(k)
            for i in range(k+k, nmax+1, k):
                fl[i] = False
        k += 2            

def cost_gen1(money, lvl=0, lst=[]):
    uc = unit_cost[lvl]
    if lvl==len(unit_cost)-1:
        yield uc * math.floor(money/uc)
    else:
        for i in range(int(money/uc),-1,-1):
            tot_uc = uc*i
            rem = money - tot_uc
            if rem < unit_cost[lvl+1]:
                yield tot_uc
            else:
                for j in cost_gen1(rem, lvl+1):
                    yield  j + tot_uc

def check_mutually_prime(v):
    s = min(v)
    for i in range(2,s+1):
        if sum(map(lambda x:x%i, v))==0:
            return False
    return True
    
def main():
    global unit_cost, total_cost, primes, pmax
    if not Debug:
        fh=sys.stdin
    else:
        #fh=open('vol2_0202b.txt', 'r')
        fh=open('vol2_0202.txt', 'r')
        pdb.set_trace()
    if True:
        primes=[x for x in prime() if x<nmax+1]
    else:
        for i in prime():
            primes.append(i)
            if i >= nmax:
                break
    while True:
        m, total_cost = list(map(int, fh.readline().strip().split()))
        if m==0 and total_cost==0:
            break
        v=[]
        for _ in range(m):
            v.append(int(fh.readline()))
        unit_cost = sorted(v, reverse=True)   # 大きい順
        # 互いに素(relative prime)、でないときの処理
        if not check_mutually_prime(unit_cost):
            print('NA')
            continue
        t0=time.time()
        p=[]
        pmax=-1
        gen=cost_gen1(total_cost, 0)
        for i in gen:
            if i > pmax and i in primes:
                p.append(i)
                pmax=max(p)
                if pmax==total_cost:
                    break
        print(max(p))
            
        if Debug:
            print('t=', time.time()-t0)
    fh.close()
	            
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import pdb
import sys,math,time

#Debug=True
Debug=False
nmax=1000000
#unit_cost = [500,305,260,129]
#total_cost = 15000
#unit_cost = [12,9,5]
#total_cost = 200909
unit_cost = []
total_cost=0
primes=[]
pmax=-1

dic = {2:True,3:True}
def prime3(n):
    global dic
    if n in dic:
        return(dic[n])
    else:
        if n % 2==0:
            return False
        while True:
            for i in range(3,math.ceil(math.sqrt(n))+1,2):
                if n % i == 0:
                    dic[n]=False
                    return(False)
            dic[n]=True
            return(True)

def cost_gen1(money, lvl=0, lst=[]):
    uc = unit_cost[lvl]
    if lvl==len(unit_cost)-1:
        yield uc * math.floor(money/uc)
    else:
        for i in range(int(money/uc),-1,-1):
            tot_uc = uc*i
            rem = money - tot_uc
            if rem < unit_cost[lvl+1]:
                yield tot_uc
            else:
                for j in cost_gen1(rem, lvl+1):
                    yield  j + tot_uc

def check_mutually_prime(v):
    s = min(v)
    for i in range(2,s+1):
        if sum(map(lambda x:x%i, v))==0:
            return False
    return True
    
def main():
    global unit_cost, total_cost, primes, pmax
    if not Debug:
        fh=sys.stdin
    else:
        #fh=open('vol2_0202b.txt', 'r')
        fh=open('vol2_0202.txt', 'r')
        pdb.set_trace()

    while True:
        m, total_cost = list(map(int, fh.readline().strip().split()))
        if m==0 and total_cost==0:
            break
        v=[]
        for _ in range(m):
            v.append(int(fh.readline()))
        unit_cost = sorted(v, reverse=True)   # 大きい順
        # 互いに素(relative prime)、でないときの処理
        if not check_mutually_prime(unit_cost):
            print('NA')
            continue
        t0=time.time()
        p=[]
        pmax=-1
        gen=cost_gen1(total_cost, 0)
        for i in gen:
            #if i > pmax and i in primes:
            if i > pmax and prime3(i):
                p.append(i)
                pmax=max(p)
                if pmax==total_cost:
                    break
        print(max(p))
            
        if Debug:
            print('t=', time.time()-t0)
    fh.close()
	            
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys,math,time

#Debug=True
Debug=False
nmax=1000000
unit_cost = []
total_cost=0
primes=[]
pmax=-1
dic = {2:True,3:True}

def prime3(n):
    global dic
    if n in dic:
        return(dic[n])
    else:
        if n % 2==0:
            return False
        while True:
            for i in range(3,math.ceil(math.sqrt(n))+1,2):
                if n % i == 0:
                    dic[n]=False
                    return(False)
            dic[n]=True
            return(True)

def cost_gen1(money, lvl=0, lst=[]):
    uc = unit_cost[lvl]
    if lvl==len(unit_cost)-1:
        yield uc * math.floor(money/uc)
    else:
        for i in range(int(money/uc),-1,-1):
            tot_uc = uc*i
            rem = money - tot_uc
            if rem < unit_cost[lvl+1]:
                yield tot_uc
            else:
                for j in cost_gen1(rem, lvl+1):
                    yield  j + tot_uc

def check_mutually_prime(v):
    s = min(v)
    for i in range(2,s+1):
        if sum(map(lambda x:x%i, v))==0:
            return False
    return True
    
def main():
    global unit_cost, total_cost, primes, pmax
    if not Debug:
        fh=sys.stdin
    else:
        #fh=open('vol2_0202b.txt', 'r')
        fh=open('vol2_0202.txt', 'r')
        #pdb.set_trace()

    while True:
        m, total_cost = list(map(int, fh.readline().strip().split()))
        if m==0 and total_cost==0:
            break
        v=[]
        for _ in range(m):
            v.append(int(fh.readline()))
        unit_cost = sorted(v, reverse=True)   # 大きい順
        # 互いに素(relative prime)、でないときの処理
        if not check_mutually_prime(unit_cost):
            print('NA')
            continue
        t0=time.time()
        p=[]
        pmax=-1
        gen=cost_gen1(total_cost, 0)
        for i in gen:
            #if i > pmax and i in primes:
            if i > pmax and prime3(i):
                p.append(i)
                pmax=max(p)
                if pmax==total_cost:
                    break
        print(max(p))
            
        if Debug:
            print('t=', time.time()-t0)
    fh.close()
	            
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys,math

#Debug=True
Debug=False
nmax=1000000
unit_cost = []
total_cost=0
primes=[]
pmax=-1
dic = {2:True,3:True}

def prime3(n):
    global dic
    if n in dic:
        return(dic[n])
    else:
        if n % 2==0:
            return False
        while True:
            for i in range(3,math.ceil(math.sqrt(n))+1,2):
                if n % i == 0:
                    dic[n]=False
                    return(False)
            dic[n]=True
            return(True)

def cost_gen1(money, lvl=0, lst=[]):
    uc = unit_cost[lvl]
    if lvl==len(unit_cost)-1:
        yield uc * math.floor(money/uc)
    else:
        for i in range(int(money/uc),-1,-1):
            tot_uc = uc*i
            rem = money - tot_uc
            if rem < unit_cost[lvl+1]:
                yield tot_uc
            else:
                for j in cost_gen1(rem, lvl+1):
                    yield  j + tot_uc

def check_mutually_prime(v):
    s = min(v)
    for i in range(2,s+1):
        if sum(map(lambda x:x%i, v))==0:
            return False
    return True
    
def main():
    global unit_cost, total_cost, primes, pmax
    if not Debug:
        fh=sys.stdin
    else:
        #fh=open('vol2_0202b.txt', 'r')
        fh=open('vol2_0202.txt', 'r')
        #pdb.set_trace()

    while True:
        m, total_cost = list(map(int, fh.readline().strip().split()))
        if m==0 and total_cost==0:
            break
        v=[]
        for _ in range(m):
            v.append(int(fh.readline()))
        unit_cost = sorted(v, reverse=True)   # 大きい順
        # 互いに素(relative prime)、でないときの処理
        if not check_mutually_prime(unit_cost):
            print('NA')
            continue
        #t0=time.time()
        p=[]
        pmax=-1
        gen=cost_gen1(total_cost, 0)
        for i in gen:
            #if i > pmax and i in primes:
            if i > pmax and prime3(i):
                p.append(i)
                pmax=max(p)
                if pmax==total_cost:
                    break
        print(max(p))
            
        #if Debug:
        #    print('t=', time.time()-t0)
    fh.close()
	            
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from math import sqrt, ceil
#Debug=True
Debug=False
nmax=1000000
nmax1=nmax+1
def nums(unit_cost, total_cost):
    cand = [True if i==0 else False for i in range(total_cost+1)]
    for i in range(total_cost+1):
        if cand[i]:
            for j in unit_cost:
                if i + j <= total_cost:
                    cand[i+j]=True
    return(cand)

dic = {2:True}
def prime3(n):
    if n in dic:
        return(dic[n])
    else:
        if n % 2==0:
            return False
        while True:
            for i in range(3,ceil(sqrt(n))+1,2):
                if n % i == 0:
                    dic[n]=False
                    return(False)
            dic[n]=True
            return(True)
    
def main():
    if Debug:
        fh=open('vol2_0202.txt', 'r')
    else:
        fh=sys.stdin

    while True:
        m, total_cost = list(map(int, fh.readline().strip().split()))
        if m==0:
            break
        v=[]
        for _ in range(m):
            v.append(int(fh.readline()))
        unit_cost = sorted(v)

        cand = nums(unit_cost, total_cost)
        for i in range(total_cost,-1,-1):
            if cand[i] and prime3(i):
                print(i)
                break
        if i==0:
            print("NA")

    fh.close()
	            
if __name__ == "__main__":
    main()