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: Wrong Answer

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

#Debug=True
Debug=False
nmax=1000000
unit_cost = []
total_cost=0
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, 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:
            break
        v=[]
        for _ in range(m):
            v.append(int(fh.readline()))
        unit_cost = sorted(v, reverse=True)   # 大きい順
        print('NA')
        continue


        # 互いに素(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 prime3(i):
                p.append(i)
                pmax=max(p)
                if pmax==total_cost:
                    break
        print(pmax)
            
        #if Debug:
        #    print('t=', time.time()-t0)
    fh.close()
	            
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

#Debug=True
Debug=False
nmax=1000000
unit_cost = []
total_cost=0
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, 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:
            break
        v=[]
        for _ in range(m):
            v.append(int(fh.readline()))
        unit_cost = sorted(v, reverse=True)   # 大きい順
        print('NA')
        continue


        # 互いに素(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 prime3(i):
                p.append(i)
                pmax=max(p)
                if pmax==total_cost:
                    break
        print(pmax)
            
        #if Debug:
        #    print('t=', time.time()-t0)
    fh.close()
	            
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

#Debug=True
Debug=False
nmax=1000000
unit_cost = []
total_cost=0
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, 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:
            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()
        print('NA')
        continue

        p=[]
        pmax=-1
        gen=cost_gen1(total_cost, 0)
        for i in gen:
            if i > pmax and prime3(i):
                p.append(i)
                pmax=max(p)
                if pmax==total_cost:
                    break
        print(pmax)
            
        #if Debug:
        #    print('t=', time.time()-t0)
    fh.close()
	            
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

#Debug=True
Debug=False
nmax=1000000
unit_cost = []
total_cost=0
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=[]):
    try:
        uc = unit_cost[lvl]
        if lvl==len(unit_cost)-1:
            yield uc * (money//uc)
        else:
            for i in range(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
    except Exception:
        print('NA')
    

    

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, 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:
            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()
    #    print('NA')
    #    continue

        p=[]
        pmax=-1
        gen=cost_gen1(total_cost, 0)
        for i in gen:
            if i > pmax and prime3(i):
                p.append(i)
                pmax=max(p)
                if pmax==total_cost:
                    break
        print(pmax)
            
        #if Debug:
        #    print('t=', time.time()-t0)
    fh.close()
	            
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

#Debug=True
Debug=False
nmax=1000000
unit_cost = []
total_cost=0
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=[]):
#    try:
        uc = unit_cost[lvl]
        if lvl==len(unit_cost)-1:
            yield uc * (money//uc)
        else:
            for i in range(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
 #   except Exception:
 #       print('NA')
    

    

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, 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:
            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()
    #    print('NA')
    #    continue

        p=[]
        pmax=-1
        gen=cost_gen1(total_cost, 0)
        for i in gen:
            if i > pmax and prime3(i):
                p.append(i)
                pmax=max(p)
                if pmax==total_cost:
                    break
        print(pmax)
            
        #if Debug:
        #    print('t=', time.time()-t0)
    fh.close()
	            
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

#Debug=True
Debug=False
nmax=1000000
unit_cost = []
total_cost=0
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=[]):
#    try:
        uc = unit_cost[lvl]
        if lvl==len(unit_cost)-1:
            yield uc * (money//uc)
        else:
            for i in range(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
 #   except Exception:
 #       print('NA')
    

    

def check_mutually_prime(v):
    if sum(map(lambda x:x%2, v))==0:
        return False
    s = min(v)
    for i in range(3,int(math.sqrt(s))+1,2):
        if sum(map(lambda x:x%i, v))==0:
            return False
    return True
    
def main():
    global unit_cost, total_cost, 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:
            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()
    #    print('NA')
    #    continue

        p=[]
        pmax=-1
        gen=cost_gen1(total_cost, 0)
        for i in gen:
            if i > pmax and prime3(i):
                p.append(i)
                pmax=max(p)
                if pmax==total_cost:
                    break
        print(pmax)
            
        #if Debug:
        #    print('t=', time.time()-t0)
    fh.close()
	            
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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: Wrong Answer

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)]
    costs = [c for c in costs if not any((c % cc == 0) and (c != cc) for cc in costs)]
    if reduce(gcd, costs) != 1 or len(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: Wrong Answer

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)
            
    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: Wrong Answer

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
            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: Wrong Answer

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
            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: Wrong Answer

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))):
        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 = 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:
""" Created by Jieyi on 9/6/16. """


def primes(n):
    if n == 2:
        return [2]
    elif n < 2:
        return []
    s = list(range(3, n + 1, 2))
    mroot = n ** 0.5
    half = (n + 1) / 2 - 1
    i = 0
    m = 3
    while m <= mroot:
        if s[i]:
            j = int((m * m - 3) / 2)
            s[j] = 0
            while j < half:
                if j >= len(s):
                    j += m
                    continue
                s[j] = 0
                j += m
        i += 1
        m = 2 * i + 3
    return [2] + [x for x in s if x]


prime = primes(1000000)


def mark_array(index, arr_list, price_list):
    for t in price_list:
        if index + t < len(arr_list):
            arr_list[index + t] = 1


def algorithm():
    while True:
        n, total = map(int, input().split())
        if n == 0 and total == 0:
            break

        price = []
        arr_list = [0 for _ in range(total + 1)]

        for i in range(n):
            price.append(int(input()))

        for i in range(len(arr_list)):
            for p in price:
                if arr_list[i] == 0 and i % p == 0:
                    arr_list[i] = 1
                    mark_array(i, arr_list, price)
                elif arr_list[i] == 1:
                    mark_array(i, arr_list, price)

        if all(arr_list):
            print('NA')
        else:
            for i in range(total, -1, -1):
                if arr_list[i] == 1:
                    if i in prime:
                        print(i)
                        break
                if i == 0:
                    print('NA')


def main():
    algorithm()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def sieve(n):
    p=0
    prime=[0]*n
    is_prime=[True]*(n+1)
    is_prime[0]=is_prime[1]=False
    for i in xrange(2,n+1):
        if is_prime[i]:
            p+=1
            prime[p]=i
            for j in xrange(2*i,n+1,i):
                is_prime[j]=False
    return prime,p

def solve():
    prime,p=sieve(x)
    m=[int(raw_input()) for _ in xrange(n)]
    dp=[False]*(x+1)
    dp[0]=True
    for i in xrange(n):
        for j in xrange(m[i],x+1):
            dp[j]=dp[j]|dp[j-m[i]]

    for i in xrange(p,0,-1):
        if dp[prime[i]]:
            return prime[i]
    return -1

while 1:
    n,x=map(int,raw_input().split())
    if n==x==0:break
    ans=solve()
    if ans==-1:
        print("NA")
    else:
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
def sieve(n):
    p=0
    prime=[True]*(n+1)
    prime[0]=prime[1]=False
    for i in xrange(2,n+1):
        if prime[i]:
            p=i
            prime[i]=i
            for j in xrange(2*i,n+1,i):
                prime[j]=False
    return prime,p

def solve():
    prime,p=sieve(x)
    m=[int(raw_input()) for _ in xrange(n)]
    dp=[False]*(x+1)
    dp[0]=True
    for i in xrange(n):
        for j in xrange(m[i],prime[p]+1):
            dp[j]=dp[j]|dp[j-m[i]]

    for i in xrange(p,0,-1):
        if prime[i]:
            if dp[prime[i]]:
                return prime[i]
    return -1

while 1:
    n,x=map(int,raw_input().split())
    if n==x==0:break
    ans=solve()
    if ans==-1:
        print("NA")
    else:
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
def sieve(n):
    prime=[]
    is_prime=[True]*(n+1)
    is_prime[0]=is_prime[1]=False
    for i in xrange(2,n+1):
        if is_prime[i]:
            prime.append(i)
            for j in xrange(2*i,n+1,i):
                is_prime[j]=False
    return prime

def solve():
    prime=sieve(x)
    m=[int(raw_input()) for _ in xrange(n)]
    dp=[False]*(x+1)
    dp[0]=True
    for i in xrange(n):
        for j in xrange(m[i],prime[-1]+1):
            dp[j]=dp[j]|dp[j-m[i]]

    for i in reversed(prime):
        if dp[i]:
            return i,True
    return 0,False

while 1:
    n,x=map(int,raw_input().split())
    if n==x==0:break
    ans,judge=solve()
    print(ans if judge else 'NA')

Submission status: Time Limit Exceeded

Solution code:
def solve():
    m=[int(raw_input()) for _ in xrange(n)]
    dp=[False]*(x+1)
    dp[0]=True
    for i in xrange(n):
        for j in xrange(m[i],x+1):
            dp[j]=dp[j]|dp[j-m[i]]

    for i in reversed(prime):
        if x<i:continue
        if dp[i]:
            return i,True
    return 0,False

n=10**7
prime=[]
is_prime=[True]*(n+1)
is_prime[0]=is_prime[1]=False
for i in xrange(2,n+1):
    if is_prime[i]:
        prime.append(i)
        for j in xrange(2*i,n+1,i):
            is_prime[j]=False
print prime
while 1:
    n,x=map(int,raw_input().split())
    if n==x==0:break
    ans,judge=solve()
    print(ans if judge else 'NA')

Submission status: Time Limit Exceeded

Solution code:
p=[0]*2+[1]*999999	
for i in range(2,int(1000001**0.5)+1):
    if p[i]:
        for j in range(i*i,1000001,i):
            p[j]=0
while 1:
    n,x=map(int,input().split())
    if n==0:break
    dp=[1]+[0]*(x)
    for i in range(n):
        a=int(input())
        for j in range(a,x+1):
            if dp[j-a]:dp[j]=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:
def is_prime(n):
    i=2
    while i*i<=n:
        if n%i== 0:return 0
        i+=1
    return 1

while 1:
    n,x=map(int,input().split())
    if n==0:break
    dp=[1]+[0]*(x)
    for i in range(n):
        a=int(input())
        for j in range(a,x+1):
            if dp[j-a]:dp[j]=1
    for i in range(x,1,-1):
        if is_prime(i) and dp[i]:print(i);break
    else:print('NA')

Submission status: Time Limit Exceeded

Solution code:
def Prime():
    p=[0]*2+[1]*999999
    n = len(p)
    def prime(x):
        for i in range(x + x, n, x):
            p[i] = 0
    prime(2);prime(3);prime(5);prime(7)
    prime(11);prime(13)
    for i in range(15, int(n**0.5)+1,2):
        if (i % 2 and i % 3  and i % 5 and
            i % 7 and i % 11 and i % 13):
            for j in range(i * i, n, i):
                p[j] = 0
    return p

p=Prime()
while 1:
    n,x=map(int,input().split())
    if n==0:break
    dp=[1]+[0]*(x)
    for i in range(n):
        a=int(input())
        for j in range(a,x+1):
            if dp[j-a]:dp[j]=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:
def Prime():
    p=[0]*2+[1]*999999
    n = len(p)
    def prime(x):
        for i in range(x + x, n, x):
            p[i] = 0
    prime(2);prime(3);prime(5);prime(7)
    prime(11);prime(13)
    for i in range(15, int(n**0.5)+1,2):
        if (i % 2 and i % 3  and i % 5 and
            i % 7 and i % 11 and i % 13):
            for j in range(i * i, n, i):
                p[j] = 0
    return p
 
p=Prime()
while 1:
    n,x=map(int,input().split())
    if n==0:break
    dp=[1]+[0]*(x)
    for i in range(n):
        a=int(input())
        for j in range(a,x+1):
            if dp[j-a]:dp[j]=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:
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
    for _ in xrange(n):
        c = int(raw_input())
        for i in xrange(x + 1 - c):
            if dp[i]:
                dp[i + c] = True
    print (["NA"] + filter(lambda x: dp[x] and isPrime[x], xrange(x + 1)))[-1]

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
    for _ in xrange(n):
        c = int(raw_input())
        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