Problem: Taro Aizu's company has a boss who hates being indivisible. When Taro goes out to eat with his boss, he pays by splitting the bill, but when the payment amount is not divisible by the number of participants, his boss always pays for it.

One day, Taro became the secretary of the dinner party. Mr. Taro, who has little money, wondered if he could invite his boss to get a treat. I have to place an order with a restaurant, but I don't know how many people will participate yet, so it seems that I want to place an order so that any number of people can participate. At the same time as Mr. Taro, you who are also planning to attend the dinner party decided to cooperate with Mr. Taro to calculate the amount that is less than the budget amount and is not divisible by any number of people.

Create a program that inputs the type of dish, the price of each dish, and the budget amount, and outputs the total amount (excluding 1 and the total amount) that is not divisible by any number that is less than or equal to the budget amount. You can order multiple dishes of each type, but you do not have to order all types of dishes. However, if there is no such total amount, output NA.



Input

A sequence of multiple datasets is given as input. The end of the input is indicated by two lines of zeros. Each dataset is given in the following format:


n x
v1
v2
::
vn


On the first line, the type of dish n (1 ≤ n ≤ 30) and the budget amount x (1 ≤ x ≤ 1000000) are given, separated by blanks. The next n lines are given the integer vi (1 ≤ vi ≤ 1000000), which represents the amount of the i-type dish.

The number of datasets does not exceed 100.

Output

For each input dataset, print the total amount or NA closest to the budget amount on one line.

Example

Input

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


Output

14983
NA
200909

Solution (in JAVA):

Solution:
import java.util.Map.Entry;
import java.io.*;
import java.util.*;

public class Main {
	
	public static void main(String[] args) throws IOException {
		FastScanner sc = new FastScanner(System.in);
		
		int MAX = 1000000;
		boolean[] isPrime = new boolean[MAX+1];
		Arrays.fill(isPrime, true);
		isPrime[0] = false;
		isPrime[1] = false;
		for(int i = 2; i <= MAX; i++){
			if(isPrime[i]){
				for(int j = i + i; j <= MAX; j += i)
					isPrime[j] = false;
			}
		}
		
		while(true){
			int n = sc.nextInt();
			int x = sc.nextInt();
			if(n == 0 && x == 0) break;
			int[] v = new int[n+1];
			for(int i = 1; i <= n; i++) v[i] = sc.nextInt();
			
			boolean[] dp = new boolean[x+1];
			dp[0] = true;
			int ans = -1;
			
			for(int i = 0; i <= x; i++){
				if(dp[i]){
					for(int j = 1; j <= n; j++){
						if(i+v[j] <= x)
							dp[i+v[j]] = true;
					}
				}
			}
			
			for(int i = x; i >= 0; i--){
				if(dp[i] && isPrime[i]){
					ans = i;
					break;
				}
			}
			
			if(ans == -1)
				System.out.println("NA");
			else
				System.out.println(ans);
			
			
		}
	}
	
	public static void solve(Scanner sc){
		
		
	}
}

class FastScanner {
    private InputStream in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    public FastScanner(InputStream in) {
		this.in = in;
	}
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() {
    	if (hasNextByte()) return buffer[ptr++];
    	else return -1;
    }
    private static boolean isPrintableChar(int c){
    	return 33 <= c && c <= 126;
    }
    public boolean hasNext() {
    	while(hasNextByte() && !isPrintableChar(buffer[ptr]))
    		ptr++; return hasNextByte();
    }
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() {
    	return Double.parseDouble(next());
    }
}