import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.*;

public class test2 {

	// selectionSortx3
	//
	// This method takes three arrays and sorts them according to the first array (x)
	//
	// In this program x will always be the Value / Mass ratios for a given problem set
	// thus Y and Z will always represent value array and mass array for the problem set
	//
	// Hence Y and Z will be sorted in a way to match the values with the V/M array thus
	// organizing the problem

	public static void selectionSortx3(double[] x, int[] y, int[] z) {
		int temp;
		double dtemp;
		for (int i=0; i<x.length-1; i++) {
	        for (int j=i+1; j<x.length; j++) {
	            if (x[i] < x[j]) {
	                //... Exchange elements
	                dtemp = x[i];
	                x[i] = x[j];
	                x[j] = dtemp;
	                temp = y[i];
	                y[i] = y[j];
	                y[j] = temp;
	                temp = z[i];
	                z[i] = z[j];
	                z[j] = temp;
	            }
	        }
	    }
	}

	// Find the greedy result, since the elements are sorted just take the first elements until there's no more space
	// this is different from the FFC because the FFC finds the opposite of greedy.
	public static int greedy (double[] vmratio, int[]masses, int[]values, int[] capacity, int index){
		int FFCvar = 0;
		int load = capacity [0];

		for (int i = index; i < values.length; i++){
			if (masses[i] <= load){
				load -= masses[i];
			} else {
				FFCvar += values[i];
			}
		}
		return FFCvar;
	}

	// calculate the GFC, this is the value of any items that are individually
	// too heavy (too much mass)
	public static int GFC (int[]masses, int[]values, int capacity, int index){
		int GFCvar = 0;
//		int load = capacity;

		for (int i = index; i < masses.length; i++){
			if (masses[index] > capacity){
				GFCvar += values[index];
			}
		}
		return GFCvar;
	}

	// calculate the value of any object that you have previously decided
	// not to take
	public static int CSF (int[] havepicked, int[]valuesarr){

		int CSFvar = 0;
		for (int i = 0; i < valuesarr.length; i++){
			if (havepicked[i+1] == 2){
				CSFvar += valuesarr[i];
			}
		}

		return CSFvar;
	}


	public static int FFC (int[] havepicked, int[]valuesarr, int[]masses, int capacity, int index){
		int FFCvar = 0;
		int load = capacity;

		for (int i = index; i < valuesarr.length; i++){
			if (masses[i] <= load){
				load -= masses[i];
			} else {
				FFCvar += valuesarr[i];
			}
		}
		return FFCvar;
	}

	public static int[] solve (double[] vmratio, int[]masses, int[]values, int[] capacity){
		boolean notfound = true;
		int indexPtr = 0;
		int GUB;
		int thiscsf;
		int thisgfc;
		int thisffc;
		int tmpcnt;
		int []temp = new int[masses.length +2];
		int []dbug;
		int utemp;
		int wtemp;
		for (int i = 0; i < temp.length; i++)
			temp [i] = 0;

		MinHeap psolutions = new MinHeap(temp);
		int[] chosen;

		GUB = greedy (vmratio, masses, values, capacity, indexPtr);



//		dbug = psolutions.peek();
//		for (int i = 0; i < dbug.length; i++)
//			System.out.printf("%d ", dbug[i]);
//		System.out.println("");

		while (notfound){

			temp = psolutions.remove().clone();
			utemp = temp[0];
			wtemp = temp[1];
			tmpcnt = 0;
			indexPtr = -1;
			while(indexPtr == -1){
				if (temp[tmpcnt+2] == 0){
					indexPtr = tmpcnt;
				} else {
					tmpcnt ++;
				}

				if (tmpcnt +2 >= temp.length && (temp[temp.length-1] != 0)){
					indexPtr = 0;
					notfound = false;
				}
			}

			if (notfound){
				if (temp[1] + masses[indexPtr] <= capacity[0]){
					temp[indexPtr+2] = 1;
					thiscsf = CSF(temp, values);
					thisgfc = GFC(masses, values, (capacity[0] - masses[indexPtr]) - temp[1], indexPtr+1);
					thisffc = FFC(temp, values, masses, (capacity[0] - masses[indexPtr]) - temp[1], indexPtr+1);

					if (thiscsf+thisgfc == GUB){

						temp[0] = thiscsf + thisgfc;

						temp[1] += masses[indexPtr];

						psolutions.add(temp);

						if (thiscsf+thisffc < GUB){
							GUB = thiscsf+thisffc;
						}

					} else if (thiscsf+thisgfc < GUB){
						temp[0] = thiscsf + thisgfc;
						temp[1] += masses[indexPtr];
						psolutions.add(temp.clone());
						if (thiscsf+thisffc < GUB){
							GUB = thiscsf+thisffc;
						}
					}

				}

				temp[0] = utemp;
				temp[1] = wtemp;
				temp[indexPtr+2] = 2;

				thiscsf = CSF(temp, values);

				thisgfc = GFC(masses, values, capacity[0] - temp[1], indexPtr+1);

				thisffc = FFC(temp, values, masses, capacity[0]- temp[1], indexPtr+1);

				if (thiscsf+thisgfc == GUB){
					temp[0] = thiscsf + thisgfc;
					psolutions.add(temp);
					if (thiscsf+thisffc < GUB){
						GUB = thiscsf+thisffc;
					}
				} else if (thiscsf+thisgfc < GUB){
					temp[0] = thiscsf + thisgfc;
					psolutions.add(temp);
					if (thiscsf+thisffc < GUB){
						GUB = thiscsf+thisffc;
					}
				}

			}// end selection structure which wraps expansion
			 // the selection structure prevents expansion after
			 // an optimal, fully expanded solution is chosen.

		}

		chosen = temp.clone();

		return chosen.clone();
	}
	/**
	 * @param args
	 * @throws FileNotFoundException
	 */
	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub

		int[] mutableCL = new int[1];

		int instances;
		int[] carrylimit;
		int[] numobj;
		int[][]objmasses;
		int[][]objvalues;
		int[]solution;

		double[][] vmr;

		Scanner inputScan = new Scanner(new BufferedReader(new FileReader("Lab_9_data.txt")));

		instances = inputScan.nextInt();

		carrylimit = new int[instances];
		numobj = new int[instances];
		objmasses = new int[instances][];
		objvalues = new int[instances][];
		vmr = new double[instances][];
		for (int i = 0; i < instances; i++){
			carrylimit[i] = inputScan.nextInt();
			numobj[i] = inputScan.nextInt();
			objmasses[i] = new int[numobj[i]];
			objvalues[i] = new int[numobj[i]];
			vmr[i] = new double [numobj[i]];

			for (int j = 0; j < numobj[i]; j++){
				objmasses[i][j] = inputScan.nextInt();
			} // initialize the masses for each problem
			for (int j = 0; j < numobj[i]; j++){
				objvalues[i][j] = inputScan.nextInt();
			} // initialize the values for each problem

		} // initialize the data

		inputScan.close();

		for (int i = 0; i < instances; i++){
			for (int j = 0; j < numobj[i]; j++){
				vmr [i][j] = ((double)objvalues[i][j])/((double)objmasses[i][j]);
			}
		} // initialize the value/mass ratio array

		// sort the value/mass ratio arrays and adjust the value and mass arrays
		// to match the v/m ratio array
		for (int i = 0; i < instances; i++){

			for (int j = 0; j < numobj[i]; j++){
				vmr [i][j] = ((double)objvalues[i][j])/((double)objmasses[i][j]);
			}

		}


		for (int i = 0; i < instances; i++)
			selectionSortx3(vmr[i], objmasses[i], objvalues[i]);




		for (int i = 0; i < instances; i++){
			mutableCL[0] = carrylimit[i];

			solution = solve(vmr[i], objmasses[i], objvalues[i], mutableCL).clone();

			System.out.printf("\nFor instance %d the solution is as follows:\n", i+1);

			for (int j = 2; j < solution.length; j++){
				if (solution[j] == 1)
					System.out.printf("Take item #%d with %d mass and %d value\n", j-1, objmasses[i][j-2], objvalues[i][j-2]);
			}

		}

	}


}