di chuyen bo

package day5_0506;

import java.util.Scanner;

public class move_cow {
	
	static int[] wcows;
	static int n, max;
	
	private static void sinh(int[] binary, int i, int w){
		for(int j = 0; j < 2; j++){
			binary[i] = j;
			if(i == n - 1){
				int sum = 0;
				for(int k = 0; k < n; k++){
					sum += binary[k] * wcows[k];
				}
				if(sum < w && max < sum) max = sum;
			}
			else sinh(binary, i + 1, w);
			
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int testcase = sc.nextInt();
		for(int tc = 1; tc <= testcase; tc++){
			int w = sc.nextInt(); n = sc.nextInt();
			wcows = new int[n];
			for(int i = 0; i < n; i++){
				wcows[i] = sc.nextInt();
			}
			int[] binary = new int[n];
			max = 0;
			sinh(binary, 0, w);
			
			System.out.println("#" + tc + " " + max);
			
		}
	}

}