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: 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")

    from time import sleep
    sleep(1)
    fh.close()
	            
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys,time
from math import sqrt, ceil
range=xrange
#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,int(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()
    time.sleep(1)

Submission status: Runtime Error

Solution code:
N=1000000

isPrime = [False,False]+[True]*(N-2)
isPrime[4::2] = [False]*len(isPrime[4::2])
for i in range(3,1000,2):
    if isPrime[i]:
        isPrime[2*i::i] = [False]*len(isPrime[2*i::i])

while True:
    n,g = [int(i) for i in input().split()]
    prices = [int(input()) for i in range(n)]
    if n==0: break
    isPayable = [True]+[False]*g
    for pri in prices:
        for i in range(0,g-pri):
            if isPayable[i]:
                isPayable[i+pri] = True
    for i in reversed(range(g+1)):
        if i == 0:
            print('NA')
        if isPrime[i] and isPayable[i]:
            print(i)
            break

Submission status: Runtime Error

Solution code:
N=1000000

isPrime = [False,False]+[True]*(N-2)
isPrime[4::2] = [False]*len(isPrime[4::2])
for i in range(3,1000,2):
    if isPrime[i]:
        isPrime[2*i::i] = [False]*len(isPrime[2*i::i])

while True:
    n,g = [int(i) for i in input().split()]
    prices = [int(input()) for i in range(n)]
    if n==0 and g==0: break
    isPayable = [True]+[False]*g
    for pri in prices:
        for i in range(0,g-pri):
            if isPayable[i]:
                isPayable[i+pri] = True
    for i in reversed(range(g+1)):
        if i == 0:
            print('NA')
        if isPrime[i] and isPayable[i]:
            print(i)
            break

Submission status: Runtime Error

Solution code:
N=1000000

isPrime = [False,False]+[True]*(N-2)
isPrime[4::2] = [False]*len(isPrime[4::2])
for i in range(3,1000,2):
    if isPrime[i]:
        isPrime[2*i::i] = [False]*len(isPrime[2*i::i])

while True:
    n,g = [int(i) for i in input().split()]
    prices = [int(input()) for i in range(n)]
    if n==0 and g == 0: break
    isPayable = [True]+[False]*g
    for pri in prices:
        for i in range(0,g-pri):
            if isPayable[i]:
                isPayable[i+pri] = True
    for i in reversed(range(g+1)):
        if i == 0:
            print('NA')
        if isPrime[i] and isPayable[i]:
            print(i)
            break

Submission status: Runtime Error

Solution code:
isPrime = [False,False]+[True]*(1000000-2)
isPrime[4::2] = [False]*len(isPrime[4::2])
for i in range(3,1000,2):
    if isPrime[i]:
        isPrime[2*i::i] = [False]*len(isPrime[2*i::i])

while True:
    n,x = [int(i) for i in input().split()]
    if n==0: break
    prices = [int(input()) for i in range(n)]
    isPayable = [True]+[False]*x
    for pri in prices:
        for i in range(0,x-pri):
            if isPayable[i]:
                isPayable[i+pri] = True
    li = [i for i in range(x+1) if isPayable[i] and isPrime[i]]
    print(max(li) if li else 'NA')

Submission status: Runtime Error

Solution code:
isPrime = [False,False]+[True]*(1000000-2)
isPrime[4::2] = [False]*len(isPrime[4::2])
for i in range(3,1000,2):
    if isPrime[i]:
        isPrime[2*i::i] = [False]*len(isPrime[2*i::i])

while True:
    n,x = [int(i) for i in input().split()]
    if n==0: break
    prices = [int(input()) for i in range(n)]
    isPayable = [True]+[False]*x
    for pri in prices:
        for i in range(0,x-pri+1):
            if isPayable[i]:
                isPayable[i+pri] = True
    li = [i for i in range(x+1) if isPayable[i] and isPrime[i]]
    print(max(li) if li else 'NA')

Submission status: Runtime Error

Solution code:
while True:
    n,x = [int(i) for i in input().split()]
    if n==0: break
    prices = [int(input()) for i in range(n)]

    isPrime = [False,False]+[True]*(x-1) # x+1
    isPrime[4::2] = [False]*len(isPrime[4::2])
    for i in range(3,int(x**0.5)+1,2):
        if isPrime[i]:
            isPrime[2*i::i] = [False]*len(isPrime[2*i::i])

    isPayable = [True]+[False]*x # x+1
    for pri in prices:
        for i in range(0,x-pri+1):
            if isPayable[i]:
                isPayable[i+pri] = True

    li = [i for i in range(x+1) if isPayable[i] and isPrime[i]]
    print(max(li) if li else 'NA')

Submission status: Runtime Error

Solution code:
isPrime = [False,False]+[True]*(1000000)
isPrime[4::2] = [False]*len(isPrime[4::2])
for i in range(3,1000,2):
    if isPrime[i]:
        isPrime[2*i::i] = [False]*len(isPrime[2*i::i])

while True:
    n,x = [int(i) for i in input().split()]
    if n==0: break
    prices = [int(input()) for i in range(n)]
    isPayable = [False]*(x+1)
    for pri in prices:
        isPayable[pri] = True
        for i in range(0,x-pri+1):
            if isPayable[i]:
                isPayable[i+pri] = True
    li = [i for i in range(x+1) if isPayable[i] and isPrime[i]]
    print(max(li) if li else 'NA')

Submission status: Runtime Error

Solution code:
isPrime = [False,False]+[True]*(1000000)
isPrime[4::2] = [False]*len(isPrime[4::2])
for i in range(3,1000,2):
    if isPrime[i]:
        isPrime[2*i::i] = [False]*len(isPrime[2*i::i])

while True:
    n,x = [int(i) for i in input().split()]
    if n==0: break
    prices = [int(input()) for i in range(n)]
    isPayable = [False]*(x+1)
    for pri in prices:
        isPayable[pri] = True
        for i in range(0,x-pri+1):
            if isPayable[i]:
                isPayable[i+pri] = True
    for i in reversed(range(x+1)):
        if isPayable[i] and isPrime[i]:
            print(i)
            break
        if i == 0:
            print('NA')

Submission status: Runtime Error

Solution code:
isPrime = [False,False]+[True]*(1000000-1) # 1,000,001
isPrime[4::2] = [False]*len(isPrime[4::2])
for i in range(3,1000,2):
    if isPrime[i]:
        isPrime[2*i::i] = [False]*len(isPrime[2*i::i])

while True:
    # n,x = [int(i) for i in input().split()]
    n,x = list(map(int, input().split()))
    if n==0 and x==0: break
    prices = [int(input()) for i in range(n)] # n
    isPayable = [False]*(x+1) # x+1
    for pri in prices:
        isPayable[pri] = True
        for i in range(0,x-pri+1):
            if isPayable[i]:
                isPayable[i+pri] = True
    for i in reversed(range(x+1)):
        if isPayable[i] and isPrime[i]:
            print(i)
            break
        if i == 0:
            print('NA')
            break

Submission status: Runtime Error

Solution code:
isPrime = [False, True] * 500000
isPrime[1:3] = [False, True]
for i in range(3, 1000, 2):
	if isPrime[i]:
		isPrime[2 * i::i] = [False] * len(isPrime[2 * i::i])

while True:
	n, x = [int(i) for i in input().split()]
	if n == 0: break
	prices = [int(input()) for i in range(n)]  # n
	isPayable = [True] + [False] * x  # x+1
	for pri in prices:
		for i in range(0, x - pri + 1):
			if isPayable[i]:
				isPayable[i + pri] = True
	li = [i for i in range(x + 1) if isPayable[i] and isPrime[i]]
	print(max(li) if li else 'NA')

Submission status: Runtime Error

Solution code:
isPrime = [False,True]*500000 # len:1,000,000
isPrime[1:3] = [False,True]
for i in range(3,1000,2):
    if isPrime[i]:
        isPrime[i*i::2*i] = [False]*len(isPrime[i*i::2*i])

n,x = map(int, input().split())
while n!=0:
    prices = [int(input()) for i in range(n)] # len:n
    isPayable = [False]*(x+1) # len:x+1
    for pri in prices:
        isPayable[pri] = True
        for i in range(0,x-pri+1):
            if isPayable[i]:
                isPayable[i+pri] = True
    li = [i for i in range(x+1) if isPayable[i] and isPrime[i]]
    print(max(li) if li else 'NA')
    n,x = map(int, input().split())

Submission status: Runtime Error

Solution code:
isPrime = [False,True]*500000 # len:1,000,000
isPrime[1:3] = [False,True]
for i in range(3,1000,2):
    if isPrime[i]:
        isPrime[i*i::2*i] = [False]*len(isPrime[i*i::2*i])

while True:
    # n,x = [int(i) for i in input().split()]
    n,x = map(int, input().split())
    if n==0 and x==0:
        import sys
        sys.exit()
    prices = [int(input()) for i in range(n)] # len:n
    isPayable = [False]*(x+1) # len:x+1
    for pri in prices:
        isPayable[pri] = True
        for i in range(0,x-pri+1):
            if isPayable[i]:
                isPayable[i+pri] = True
    li = [i for i in range(x+1) if isPayable[i] and isPrime[i]]
    print(max(li) if li else 'NA')

Submission status: Runtime Error

Solution code:
isPrime = [False,True]*500000 + [True] # len:1,000,000
isPrime[1:3] = [False,True]
for i in range(3,1000,2):
    if isPrime[i]:
        isPrime[i*i::2*i] = [False]*len(isPrime[i*i::2*i])

n,x = map(int, input().split())
while n!=0:
    prices = [int(input()) for i in range(n)] # len:n
    isPayable = [False]*(x+1) # len:x+1
    for pri in prices:
        isPayable[pri] = True
        for i in range(0,x-pri+1):
            if isPayable[i]:
                isPayable[i+pri] = True
    li = [i for i in range(x+1) if isPayable[i] and isPrime[i]]
    print(max(li) if li else 'NA')
    n,x = map(int, input().split())

Submission status: Runtime Error

Solution code:
isPrime = [False,True]*500000+[False] # len:1,000,001
isPrime[1:3] = [False,True]
for i in range(3,1000,2):
    if isPrime[i]:
        isPrime[i*i::2*i] = [False]*len(isPrime[i*i::2*i])

while True:
    n,x = map(int, input().split())
    if n==0 and x==0:
        break
    prices = [int(input()) for i in range(n)] # len:n
    isPayable = [False]*(x+1) # len:x+1
    for pri in prices:
        isPayable[pri] = True
        for i in range(0,x-pri+1):
            if isPayable[i]:
                isPayable[i+pri] = True
    li = [i for i in range(x+1) if isPayable[i] and isPrime[i]]
    print(str(max(li)) if li else 'NA')

Submission status: Runtime Error

Solution code:
# AOJ 0202: At Boss's Expense
# Python3 2018.6.26 bal4u

MAX = 1000000
SQRT = 1000     # sqrt(MAX)

not_prime = [0]*MAX
def sieve():

	for i in range(3, SQRT, 2):
		if not_prime[i] == 0:
			for j in range(i*i, MAX, i): not_prime[j] = 1
sieve()
while True:
	n, x = map(int, input().split())
	if n == 0: break
	mk, v = [0]*(x+1), [0]*n
	for i in range(n): v[i] = int(input())
	mk[0] = 1
	for k in range(x):
		if mk[k]:
			for i in range(n):
				if k+v[i] <= x: mk[k+v[i]] = 1
	ans = -1
	if x <= 2:
		if mk[x]: ans = x
	else:
		if (x & 1) == 0: x -= 1
		while x > 0:
			if mk[x] and not_prime[x] == 0:
				ans = x
				break
			x -= 2
	print(ans if ans >= 0 else "NA")

Submission status: Runtime Error

Solution code:
# AOJ 0202: At Boss's Expense
# Python3 2018.6.26 bal4u

MAX = 1000000
SQRT = 1000     # sqrt(MAX)

not_prime = [0]*(MAX+3)
def sieve():

	for i in range(3, SQRT, 2):
		if not_prime[i] == 0:
			for j in range(i*i, MAX, i): not_prime[j] = 1
sieve()

while True:
	n, x = map(int, input().split())
	if n == 0: break
	mk, v = [0]*(x+1), [0]*n
	for i in range(n): v[i] = int(input())
	mk[0] = 1
	for k in range(x):
		if mk[k]:
			for i in range(n):
				if k+v[i] <= x: mk[k+v[i]] = 1
	ans = -1
	if x <= 2:
		if mk[x]: ans = x
	else:
		if (x & 1) == 0: x -= 1
		while x > 0:
			if mk[x] and not_prime[x] == 0:
				ans = x
				break
			x -= 2
	print(ans if ans >= 0 else "NA")

Submission status: Runtime Error

Solution code:
# AOJ 0202: At Boss's Expense
# Python3 2018.6.26 bal4u

MAX = 1000000
SQRT = 1000     # sqrt(MAX)

not_prime = [0]*(MAX+3)
def sieve():
	for i in range(3, SQRT, 2):
		if not_prime[i] == 0:
			for j in range(i*i, MAX, i): not_prime[j] = 1

sieve()
v = [0]*33
while True:
	n, x = map(int, input().split())
	if n == 0: break
	mk = [0]*(x+3)
	for i in range(n): v[i] = int(input())
	mk[0] = 1
	for k in range(x):
		if mk[k]:
			for i in range(n):
				if k+v[i] <= x: mk[k+v[i]] = 1
	ans = -1
	if x <= 2:
		if mk[x]: ans = x
	else:
		if (x & 1) == 0: x -= 1
		while x > 0:
			if mk[x] and not_prime[x] == 0:
				ans = x
				break
			x -= 2
	print(ans if ans >= 0 else "NA")

Submission status: Runtime Error

Solution code:
from array import array
PRIME_MAX = 1000001
isPrime = array('b', [True] * PRIME_MAX)
isPrime[0] = isPrime[1] = False
for i in xrange(2, PRIME_MAX):
	if not isPrime[i]: continue
	for j in xrange(i << 1, PRIME_MAX, i):
		isPrime[j] = False
while True:
	n, x = map(int, raw_input().split())
	if n == x == 0: break
	menu = [input() for i in xrange(n)]
	result = 0
	exists = set()
	exists.add(0)
	for i in xrange(x + 1):
		if i in exists:
			exists.remove(i)
			for v in menu:
				exists.add(i + v)
			if isPrime[i]:
				result = i
	if result:
		print result
	else:
		print "NA"

Submission status: Runtime Error

Solution code:
from array import array
PRIME_MAX = 1000001
isPrime = array('b', [1] * PRIME_MAX)
isPrime[0] = 0
isPrime[1] = 0
for i in xrange(2, PRIME_MAX):
	if not isPrime[i]: continue
	for j in xrange(i << 1, PRIME_MAX, i):
		isPrime[j] = 0
while True:
	n, x = map(int, raw_input().split())
	if n == x == 0: break
	menu = [input() for i in xrange(n)]
	result = 0
	exists = set()
	exists.add(0)
	for i in xrange(x + 1):
		if i in exists:
			exists.remove(i)
			for v in menu:
				exists.add(i + v)
			if isPrime[i]:
				result = i
	if result:
		print result
	else:
		print "NA"

Submission status: Runtime Error

Solution code:
import sys
from array import array
PRIME_MAX = 1000001
isPrime = array('b', [True] * PRIME_MAX)
isPrime[0] = isPrime[1] = False
for i in xrange(2, PRIME_MAX):
	if not isPrime[i]: continue
	for j in xrange(i << 1, PRIME_MAX, i):
		isPrime[j] = False
sin = iter(map(int, "".join(sys.stdin.readlines()).split()))
while True:
	n = sin.next()
	x = sin.next()
	if n == x == 0: break
	menu = [sin.next() for i in xrange(n)]
	result = 0
	exists = set()
	exists.add(0)
	for i in xrange(x + 1):
		if i in exists:
			exists.remove(i)
			for v in menu:
				exists.add(i + v)
			if isPrime[i]:
				result = i
	if result:
		print result
	else:
		print "NA"

Submission status: Runtime Error

Solution code:
import sys
from array import array
PRIME_MAX = 1000010
isPrime = array('b', [True] * PRIME_MAX)
isPrime[0] = isPrime[1] = False
for i in xrange(2, PRIME_MAX):
	if not isPrime[i]: continue
	for j in xrange(i << 1, PRIME_MAX, i):
		isPrime[j] = False
sin = iter(map(int, "".join(sys.stdin.readlines()).split()))
while True:
	n = sin.next()
	x = sin.next()
	if n == x == 0: break
	menu = [sin.next() for i in xrange(n)]
	result = 0
	exists = set()
	exists.add(0)
	for i in xrange(x + 1):
		if i in exists:
			exists.discard(i)
			for v in menu:
				exists.add(i + v)
			if isPrime[i]:
				result = i
	if result:
		print result
	else:
		print "NA"

Submission status: Runtime Error

Solution code:
import sys
PRIME_MAX = 1000010
isPrime = [True] * PRIME_MAX
isPrime[0] = isPrime[1] = False
for i in xrange(2, PRIME_MAX):
	if not isPrime[i]: continue
	for j in xrange(i << 1, PRIME_MAX, i):
		isPrime[j] = False
sin = iter(map(int, "".join(sys.stdin.readlines()).split()))
while True:
	n = sin.next()
	x = sin.next()
	if n == x == 0: break
	menu = [sin.next() for i in xrange(n)]
	result = 0
	dp = [False] * (x + 1)
	dp[0] = True
	for i in xrange(x + 1):
		if dp[i]:
			for v in menu:
				if i + v <= x:
					dp[i + v] = True
			if isPrime[i]:
				result = i
	if result:
		print result
	else:
		print "NA"

Submission status: Runtime Error

Solution code:
def prime(n):
	return True if pow(2,n-1,n)==1 else False

while 1:
	n,x=map(int,raw_input().split())
	if n==0:break
	p=[input() for i in [1]*n]
	s=[0 for i in [1]*(x+1)]
	for i in p:s[i]=1
	for i in range(1,x+1):
		if s[i]==1:
			for j in p:
				try:s[i+j]=1
				except:pass
	for i in range(x,0,-1):
		if s[i]==1 and prime(i):
			print i
			break
	else:print "NA"

Submission status: Runtime Error

Solution code:
def prime(n):
	return True if pow(2,n-1,n)==1 else False

while 1:
	try:
		n,x=map(int,raw_input().split())
		if n==0:break
		p=[input() for i in [1]*n]
		s=[0 for i in [1]*(x+1)]
		for i in p:s[i]=1
		for i in range(1,x+1):
			if s[i]==1:
				for j in p:
					try:s[i+j]=1
					except:pass
		for i in range(x,0,-1):
			if s[i]==1 and prime(i):
				print i
				break
		else:print "NA"
	except SyntaxError:
		pass

Submission status: Runtime Error

Solution code:
input = raw_input

def init():
    table = [True] * 1000001
    table[0] = False
    table[1] = False
    n = len(table)
    for i in range(2, n):
        for j in range(i + i, n, i):
            table[j] = False
    return table
    
def is_prime(p):
    if p == 0 or p == 1:
        return False
    for i in range(2, p - 1):
        if p % i == 0:
            return False
    return True

def solve(price, ps, is_prime):
    dp = []
    for i in range(len(ps)):
        dp.append([False] * (price + 1))

    dp[0][ps[0]] = True
    dp[0][0]     = True

    for i in range(1, len(ps)):
        for p in range(price + 1):
            if p >= ps[i]:
                dp[i][p] = dp[i - 1][p] or dp[i][p - ps[i]]
            else:
                dp[i][p] = dp[i - 1][p]

    p = -1
    for i in range(0, price + 1):
        if is_prime[i] and dp[len(ps) - 1][i]:
            p = i
    if p == -1:
        print("NA")
    else:
        print(p)
    
def main():
    table = init()
    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, table)

main()

Submission status: Runtime Error

Solution code:
def init():
    table = [True] * 1000001
    table[0] = False
    table[1] = False
    n = len(table)
    for i in range(2, n):
        for j in range(i + i, n, i):
            table[j] = False
    return table
    
def is_prime(p):
    if p == 0 or p == 1:
        return False
    for i in range(2, p - 1):
        if p % i == 0:
            return False
    return True

def solve(price, ps, is_prime):
    dp = []
    for i in range(len(ps)):
        dp.append([False] * (price + 1))

    dp[0][ps[0]] = True
    dp[0][0]     = True

    for i in range(1, len(ps)):
        for p in range(price + 1):
            if p >= ps[i]:
                dp[i][p] = dp[i - 1][p] or dp[i][p - ps[i]]
            else:
                dp[i][p] = dp[i - 1][p]

    p = -1
    for i in range(0, price + 1):
        if is_prime[i] and dp[len(ps) - 1][i]:
            p = i
    if p == -1:
        print("NA")
    else:
        print(p)
    
def main():
    table = init()
    while True:
        n, price = map(int,raw_input().split())
        if n == 0 and price == 0:
            return
        ps = []
        for i in range(n):
            ps.append(int(raw_input()))
        solve(price, ps, table)

main()

Submission status: Runtime Error

Solution code:
input = raw_input

def init():
    table = [True] * 2000001
    table[0] = False
    table[1] = False
    n = len(table)
    for i in range(2, n):
        for j in range(i + i, n, i):
            table[j] = False
    return table
    
def is_prime(p):
    if p == 0 or p == 1:
        return False
    for i in range(2, p - 1):
        if p % i == 0:
            return False
    return True

def solve(price, ps, is_prime):
    dp = []
    for i in range(len(ps)):
        dp.append([False] * (price + 1))

    dp[0][ps[0]] = True
    dp[0][0]     = True

    for i in range(1, len(ps)):
        for p in range(price + 1):
            if p >= ps[i]:
                dp[i][p] = dp[i - 1][p] or dp[i][p - ps[i]]
            else:
                dp[i][p] = dp[i - 1][p]

    p = -1
    for i in range(0, price + 1):
        if is_prime[i] and dp[len(ps) - 1][i]:
            p = i
    if p == -1:
        print("NA")
    else:
        print(p)
    
def main():
    table = init()
    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, table)

main()

Submission status: Runtime Error

Solution code:
input = raw_input

def init():
    table = [True] * 2000001
    table[0] = False
    table[1] = False
    n = len(table)
    for i in range(2, n):
        for j in range(i + i, n, i):
            table[j] = False
    return table
    
def solve(price, ps, is_prime):
    dp = []
    for i in range(len(ps)):
        dp.append([False] * (price + 1))

    dp[0][ps[0]] = True
    dp[0][0]     = True

    for i in range(1, len(ps)):
        for p in range(price + 1):
            if p >= ps[i]:
                dp[i][p] = dp[i - 1][p] or dp[i][p - ps[i]]
            else:
                dp[i][p] = dp[i - 1][p]

    p = -1
    for i in range(0, price + 1):
        if is_prime[i] and dp[len(ps) - 1][i]:
            p = i
    if p == -1:
        print("NA")
    else:
        print(p)
    
def main():
    table = init()
    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, table)

main()

Submission status: Runtime Error

Solution code:
from datetime import datetime

def measure(f):
    measure_start = datetime.now()
    v = f()
    print(datetime.now() - measure_start)
    return v

def init():
    table = [True] * 1000001
    table[0] = False
    table[1] = False
    n = len(table)

    def prime(p):
        for i in range(p + p, n, p):
            table[i] = False
    prime(2)
    prime(3)
    prime(5)
    prime(7)
    prime(11)
    prime(13)
    
    for i in range(2, n):
        if (i % 2 != 0 and i % 3 != 0 and i % 5 != 0 and
            i % 7 != 0 and i % 11 != 0 and i % 13 != 0):
            for j in range(i + i, n, i):
                table[j] = False
    return table
    
def solve(price, ps, is_prime):
    dp = [False] * (price + 1)

    if ps[0] <= price:
        dp[ps[0]] = True
    dp[0]     = True

    for i in range(1, len(ps)):
        cur_p = ps[i]
        for p in range(price + 1):
            if p >= cur_p:
                dp[p] = dp[p] or dp[p - cur_p]

    p = -1
    for i in range(0, price + 1):
        if is_prime[i] and dp[i]:
            p = i
    if p == -1:
        print("NA")
    else:
        print(p)
    
def main():
    table = measure(lambda : init())
    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, table)

main()

Submission status: Runtime Error

Solution code:
from datetime import datetime

def measure(f):
    measure_start = datetime.now()
    v = f()
    print(datetime.now() - measure_start)
    return v

# input = raw_input
    
def init():
    table = [True] * 1000001
    table[0] = False
    table[1] = False
    n = len(table)

    def prime(p):
        for i in range(p + p, n, p):
            table[i] = False
    prime(2)
    prime(3)
    prime(5)
    prime(7)
    prime(11)
    prime(13)
    
    for i in range(2, n):
        if (i % 2 != 0 and i % 3 != 0 and i % 5 != 0 and
            i % 7 != 0 and i % 11 != 0 and i % 13 != 0):
            for j in range(i + i, n, i):
                table[j] = False
    return table
    
def solve(price, ps, is_prime):
    dp = [False] * (price + 1)

    if ps[0] <= price:
        dp[ps[0]] = True
    dp[0]     = True

    for i in range(1, len(ps)):
        cur_p = ps[i]
        for p in range(cur_p, price + 1):
            dp[p] = dp[p] or dp[p - cur_p]

    p = -1
    for i in range(0, price + 1):
        if is_prime[i] and dp[i]:
            p = i
    if p == -1:
        print("NA")
    else:
        print(p)
    
def main():
    table = measure(lambda : init())
    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, table)

main()

Submission status: Runtime Error

Solution code:
from datetime import datetime

def measure(f):
    measure_start = datetime.now()
    v = f()
    print(datetime.now() - measure_start)
    return v

# input = raw_input
# range = xrange
    
def init():
    table = [True] * 1000001
    table[0] = False
    table[1] = False
    n = len(table)

    def prime(p):
        for i in range(p + p, n, p):
            table[i] = False
    prime(2)
    prime(3)
    prime(5)
    prime(7)
    prime(11)
    prime(13)
    
    for i in range(2, n):
        if (i % 2 != 0 and i % 3 != 0 and i % 5 != 0 and
            i % 7 != 0 and i % 11 != 0 and i % 13 != 0):
            for j in range(i + i, n, i):
                table[j] = False
    return table
    
def solve(price, ps, is_prime):
    dp = [0] * ((price >> 5) + 1)

    def get(i):
        return ((dp[i >> 5] >> (i & 31)) & 1)

    def set(i, v):
        dp[i >> 5] |= (v << (i & 31))

    def get_p(i):
        return dp[i >> 5]
    def set_p(i, v):
        dp[i >> 5] |= v
        
    if ps[0] <= price:
        set(ps[0], 1)
    set(0, 1)

    for i in range(1, len(ps)):
        cur_p = ps[i]
        i1 = cur_p & 31
        rest = 0

        for p in range(cur_p, price + 1, 32):
            v = dp[(p - cur_p) >> 5]
            dp[p >> 5] |= (v << i1) | rest
            v = dp[(p - cur_p) >> 5]
            dp[p >> 5] |= (v << i1) | rest
            v = dp[(p - cur_p) >> 5]
            dp[p >> 5] |= (v << i1) | rest
            v = dp[(p - cur_p) >> 5]
            dp[p >> 5] |= (v << i1) | rest
            v = dp[(p - cur_p) >> 5]
            dp[p >> 5] |= (v << i1) | rest
            v = dp[(p - cur_p) >> 5]
            dp[p >> 5] |= (v << i1) | rest

            rest = (v >> (32 - i1)) & ((1 << i1) - 1)
            
    p = -1
    for i in range(0, price + 1):
        if is_prime[i] and get(i) == 1:
            p = i
    if p == -1:
        print("NA")
    else:
        print(p)
    
def main():
    table = measure(lambda : init())
    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, table)

main()