View Code of Problem 611

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner in =new Scanner(System.in);
		while(in.hasNext()) {
			int m =in.nextInt();
			int n =in.nextInt();
			ArrayList<int[]> key = new ArrayList<int[]>();
			int sum =0;
			for(int i =0;i<n;i++) {
				int a = in.nextInt();
				int b = in.nextInt();
				int[] ab = {a,b};
				key.add(ab);
				sum+=a*b;
			}
			if(sum>=m) {
				int step = rank(key,m,0,0);
				if(step!=Integer.MAX_VALUE) {
					System.out.println(step);
				}else {
					System.out.println("Naivete");	
				}
			}else {
				System.out.println("Naivete");			
			}
		}
	}
	public static int rank(ArrayList<int[]> key,int m,int len,int step) {
		if(len==m) {
			return step;
		}else if(len>m){
			return Integer.MAX_VALUE;
		}else {
			int min = Integer.MAX_VALUE;
			for(int[] i :key) {
				if(i[0]<=m-len && i[1]>0) {
					i[1]-=1;
					int a =rank(key,m,len+i[0],step+1);
					i[1]+=1;
					if(min>a) {
						min=a;
					}
				}
			}
			return min;
		}
	}
}