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: Time Limit Exceeded

Solution code:
MAX_X = 1000000 
isPrime = [True] * (MAX_X + 1)
isPrime[0] = isPrime[1] = False
for i in xrange(2, int(MAX_X ** 0.5) + 1):
    if isPrime[i]:
        for j in xrange(i + i, MAX_X + 1, i):
            isPrime[j] = False

while True:
    n, x = map(int, raw_input().split())
    if n | x == 0:
        break
    dp = [False] * (x + 1)
    dp[0] = True
    ans = -1
    costs = [int(raw_input()) for _ in xrange(n)]
    if all(c % 2 == 0 for c in costs):
        print "NA"
        continue
    for c in costs:
        for i in xrange(x + 1 - c):
            if dp[i]:
                dp[i + c] = True
                if isPrime[i + c]:
                    ans = max(ans, i + c)
    print "NA" if ans == -1 else ans

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
MAX_X = 1000000 
isPrime = [True] * (MAX_X + 1)
isPrime[0] = isPrime[1] = False
for i in xrange(2, int(MAX_X ** 0.5) + 1):
    if isPrime[i]:
        for j in xrange(i + i, MAX_X + 1, i):
            isPrime[j] = False

while True:
    n, x = map(int, raw_input().split())
    if n | x == 0:
        break
    dp = [False] * (x + 1)
    dp[0] = True
    ans = -1
    costs = [int(raw_input()) for _ in xrange(n)]
    if reduce(gcd, costs) != 1:
        print "NA"
        continue
    for c in costs:
        for i in xrange(x + 1 - c):
            if dp[i]:
                dp[i + c] = True
                if isPrime[i + c]:
                    ans = max(ans, i + c)
    print "NA" if ans == -1 else ans

Submission status: Time Limit Exceeded

Solution code:
while 1:
	try:
		n,x=map(int,raw_input().split())
		if n==0:break
		menu=[int(raw_input()) for i in range(n)]
		p=[0]*(x+1)
		for price in menu:
			p[price]=1
		i=1
		mm=min(menu)
		while i<x-mm:
			if p[i]==1:
				for price in menu:
					if i+price>x:break
					p[i+price]=1
			i+=1
		for i in range(x,1,-1):
			if p[i]==1 and pow(2,i-1,i)==1:
				print i
				break
		else:
			print "NA"
	except:
		pass

Submission status: Time Limit Exceeded

Solution code:
r=1000000
sqrt=int(r**0.5)
prime=[1]*(r+1)
prime[0:2]=[0,0]
prime[4::2]=[0 for i in range(3,r+1,2)]
for i in range(2,sqrt+1):
	if prime[i]:
		prime[2*i::i]=[0 for x in range(2*i,r+1,i)]

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

Submission status: Time Limit Exceeded

Solution code:
r=1000000
sqrt=int(r**0.5)
prime=[1]*(r+1)
prime[0:2]=[0,0]
prime[4::2]=[0 for i in range(3,r+1,2)]
for i in range(2,sqrt+1):
	if prime[i]:
		prime[2*i::i]=[0 for x in range(2*i,r+1,i)]

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

Submission status: Time Limit Exceeded

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

    if ps[0] <= price:
        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: Time Limit Exceeded

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 solve(price, ps, is_prime):
    dp = []
    for i in range(len(ps)):
        dp.append([False] * (price + 1))

    if ps[0] <= price:
        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: Time Limit Exceeded

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(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: Time Limit Exceeded

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: Time Limit Exceeded

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 = [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: Time Limit Exceeded

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

    if ps[0] <= price:
        set(ps[0], 1)
    set(0, 1)

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

    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()

Submission status: Time Limit Exceeded

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 = get_p(p - cur_p)
            rest = (v >> (32 - i1)) & ((1 << i1) - 1)
            set_p(p, (v << i1) | rest)
            if (rest << (32 - i1)) | (v & ((1 << (32 - i1)) - 1)) != v:
                print (rest, v, i1)
            
    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()

Submission status: Time Limit Exceeded

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 = 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: Time Limit Exceeded

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]
        r = cur_p & 31
        rest = 0
        
        for p in range(cur_p, price + 1, 32):
            i1 = (p - cur_p) >> 5
            i2 = p >> 5
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            
            rest = (v >> (32 - r)) & ((1 << r) - 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 = 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: Time Limit Exceeded

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 >> 6) + 1)

    for i in range(0, price + 1,ps[0]):
        dp[i >> 6] |= 1 << (i & 63)
    dp[0] = 1
    
    for i in range(1, len(ps)):
        cur_p = ps[i]
        r = cur_p & 63
        rest = 0
        
        for p in range(cur_p, price + 1, 64):
            i1 = (p - cur_p) >> 6
            i2 = p >> 6
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            
            rest = (v >> (64 - r)) & ((1 << r) - 1)
            
    p = -1
    for i in range(0, price + 1):
        if is_prime[i] and (dp[i >> 6] >> (i & 63)) & 1 == 1:
            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: Time Limit Exceeded

Solution code:
r = 1000001
s = int(r**0.5)
p = [1]*r
p[0] = p[1] = 0
for i in range(2,s+1):
	if p[i]:
		p[2*i::i] = [0 for _ in range(2*i,r,i)]
while 1:
	n,x = map(int,raw_input().split())
	if n == 0: break
	dish = [int(raw_input()) for i in range(n)]
	dp = [0]*(x+1)
	for i in dish:
		if i <=x:
			dp[i] = 1
	for cost in dish:
		for j in range(x-cost+1):
			if dp[j] == 1:
				dp[j+cost] = 1
	for i in range(x,1,-1):
		if p[i] and dp[i]:
			print i
			break
	else:
		print "NA"

Submission status: Time Limit Exceeded

Solution code:
r = 1000001
s = int(r**0.5)
p = [1]*r
p[0] = p[1] = 0
for i in range(2,s+1):
	if p[i]:
		p[2*i::i] = [0 for _ in range(2*i,r,i)]
while 1:
	n,x = map(int,raw_input().split())
	if n == 0: break
	dish = [int(raw_input()) for i in range(n)]
	c = 0
	pay = [0]*(x+1)
	ref = [0]*(x+1)
	for i in dish:
		if i <= x:
			pay[c] = i
			ref[i] = 1
			c += 1
	for cost in dish:
		for j in pay:
			if j == 0: break
			nwcost = j + cost
			if nwcost <= x and ref[nwcost] == 0:
				pay[c] = nwcost
				ref[nwcost] = 1
				c += 1
	for i in sorted(pay[:pay.index(0)],reverse = True):
		if p[i]:
			print i
			break
	else:
		print "NA"

Submission status: Time Limit Exceeded

Solution code:
r = 1000001
p = [1]*r
p[0] = p[1] = 0
for i in range(int(r**0.5)):
	if p[i]:
		p[2*i::i] = [0]*len(p[2*i::i])

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

Submission status: Time Limit Exceeded

Solution code:
r = 1000001
p = [1]*r
p[0] = p[1] = 0
for i in range(int(r**0.5)):
	if p[i]:
		p[2*i::i] = [0]*len(p[2*i::i])

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
r = 1000001
p = [1]*r
p[0] = p[1] = 0
for i in range(int(r**0.5)):
	if p[i]:
		p[2*i::i] = [0]*len(p[2*i::i])

while 1:
	n,x = map(int,raw_input().split())
	if n == 0: break
	menu = [int(raw_input()) for i in range(n)]
	dp = [0]*(x+1)
	check = set()
	yet = set([i for i in range(min(menu),x+1)])
	for cost in menu:
		if cost <= x:
			dp[cost] = 1
			check.add(cost)
	for cost in menu:
		ls = sorted(list(yet-check))
		for i in ls[bisect.bisect(ls,cost):]:
			if cost <= i and dp[i-cost]:
				dp[i] = 1
				check.add(i)
	for i in range(x,0,-1):
		if p[i]*dp[i]:
			print i
			break
	else:
		print "NA"

Submission status: Time Limit Exceeded

Solution code:
import bisect
r = 1000001
p = [1]*r
p[0] = p[1] = 0
for i in range(int(r**0.5)):
	if p[i]:
		p[2*i::i] = [0]*len(p[2*i::i])

while 1:
	n,x = map(int,raw_input().split())
	if n == 0: break
	menu = [int(raw_input()) for i in range(n)]
	dp = [0]*(x+1)
	check = set()
	yet = set([i for i in range(min(menu),x+1)])
	for cost in menu:
		if cost <= x:
			dp[cost] = 1
			check.add(cost)
	for cost in menu:
		ls = sorted(list(yet-check))
		for i in ls[bisect.bisect(ls,cost):]:
			if dp[i-cost]:
				dp[i] = 1
				check.add(i)
	for i in range(x,0,-1):
		if p[i]*dp[i]:
			print i
			break
	else:
		print "NA"

Submission status: Time Limit Exceeded

Solution code:
import bisect
r = 1000001
p = [1]*r
p[0] = p[1] = 0
for i in range(int(r**0.5)):
	if p[i]:
		p[2*i::i] = [0]*len(p[2*i::i])

while 1:
	n,x = map(int,raw_input().split())
	if n == 0: break
	menu = [int(raw_input()) for i in range(n)]
	cheapest = min(menu)
	dp = [0]*(x+1)
	check = set()
	yet = set([i for i in range(cheapest,x+1)])
	for cost in menu:
		if cost <= x:
			dp[cost] = 1
			check.add(cost)
	for cost in menu:
		if cost + cheapest > x: continue
		ls = sorted(list(yet-check))
		for i in ls[bisect.bisect(ls,cost+cheapest):]:
			if dp[i-cost]:
				dp[i] = 1
				check.add(i)
	for i in range(x,0,-1):
		if p[i]*dp[i]:
			print i
			break
	else:
		print "NA"

Submission status: Time Limit Exceeded

Solution code:
import bisect
r = 1000001
p = [1]*r
p[0] = p[1] = 0
for i in range(int(r**0.5)):
	if p[i]:
		p[2*i::i] = [0]*len(p[2*i::i])

while 1:
	n,x = map(int,raw_input().split())
	if n == 0: break
	menu = [int(raw_input()) for i in range(n)]
	low = min(menu)
	dp = [0]*(x+1)
	for cost in menu:
		if cost <= x:
			dp[cost] = 1
	for cost in menu:
		if cost + low > x: continue
		for i in range(low,low+cost):
			if dp[i]:
				dp[i::cost] = [1]*len(dp[i::cost])
	for i in range(x,0,-1):
		if p[i]*dp[i]:
			print i
			break
	else:
		print "NA"

Submission status: Memory Limit Exceeded

Solution code:
PRIME_MAX = 1000001
primes = set(range(2, PRIME_MAX))
for i in range(2, PRIME_MAX):
	if i not in primes: continue
	for j in range(i << 1, PRIME_MAX, i):
		primes.discard(j)

while True:
	n, x = map(int, raw_input().split())
	if n == x == 0: break
	menu = [input() for i in range(n)]
	result = 0
	exists = set((0, ))
	for i in range(x + 1):
		if i in exists:
			for v in menu:
				exists.add(i + v)
			if i in primes:
				result = i
	if result:
		print result
	else:
		print "NA"

Submission status: Memory Limit Exceeded

Solution code:
PRIME_MAX = 1000001
primes = set(xrange(2, PRIME_MAX))
for i in xrange(2, PRIME_MAX):
	if i not in primes: continue
	primes.difference_update(xrange(i << 1, PRIME_MAX, i))
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:
			for v in menu:
				exists.add(i + v)
			if i in primes:
				result = i
	if result:
		print result
	else:
		print "NA"

Submission status: Accepted

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)

    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) | 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(0, price + 1):
        if is_prime[i] and (dp[i >> 5] >> (i & 31)) & 1 == 1:
            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: Accepted

Solution code:
from datetime import datetime
import math

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, int(math.sqrt(n) + 1)):
        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
#    for i in range(len(table)):
#        if table[i]:
#            print(i)
    return table
    
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) | 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(0, price + 1):
        if is_prime[i] and (dp[i >> 5] >> (i & 31)) & 1 == 1:
            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()