import java.util.Scanner;
import java.io.*;

/*
 * Lab 6
 *
 * Author: Robin Dawes
 *
 * Date: 20081102
 *
 * Comment: 
 *
 */

public class Billboards {

    static int instances;
    static int numOfLocations;
    static Spot[] locations;
    
    static int[][] table;
 
    public static void main (String[] argv) throws Exception {
        Scanner myScanner = new Scanner(new File("Lab_6_Data.txt"));
        // find out how many instances
        instances = myScanner.nextInt();
        for (int i = 0; i < instances; i++) {
            System.out.println("\nInstance " + i + " input: ");
            numOfLocations = myScanner.nextInt();
            locations = new Spot[numOfLocations];
            
            for (int d = 0; d < numOfLocations; d++){
                    locations[d] = new Spot(myScanner.nextDouble());
                    System.out.format("%10.1f",locations[d].getDistance());                    
            }
            System.out.println();
            
            for (int d = 0; d < numOfLocations; d++){
                locations[d].setValue(myScanner.nextInt());
                System.out.format("%11d",locations[d].getValue());                
            }
            System.out.println("\n");
            
            // sort the locations based on the distance value
            
            locations = HeapSort(locations);
            
            for (int d = 0; d < numOfLocations; d++)
                System.out.format("%10.1f",locations[d].getDistance());
            System.out.println();
            
            for (int d = 0; d < numOfLocations; d++){
                System.out.format("%11d",locations[d].getValue());
            }
            System.out.println("\n");
            
            table = new int[numOfLocations][numOfLocations+1];
            
             /*
             * table[i][j] is the maximum obtainable profit using locations [0..i] without getting within 5 km of locations[j].distance
             *
             * the last column is for distance "infinity" 
             */
            
            
            // fill in the first row of the table
            
            for (int j = 0; j < numOfLocations; j++) {
                if (locations[0].getDistance() + 5 <= locations[j].getDistance()) 
                    table[0][j] = locations[0].getValue();
                else table[0][j] = 0;     
            }
            table[0][numOfLocations] = locations[0].getValue();

            // fill in the rest of the table
            
            for (int r = 1; r < numOfLocations; r++) {
                for (int c = 0; c < numOfLocations; c++) {
                    if (locations[r].getDistance() + 5 > locations[c].getDistance()) table[r][c] = table[r-1][c];
                    else {
                        table[r][c] = Math.max(table[r-1][c], 
                                                locations[r].getValue() + table[r-1][r]);
                    }
                }
                // last column treated separately since distance test is not needed
                table[r][numOfLocations] = Math.max(table[r-1][numOfLocations],
                                                     locations[r].getValue() + table[r-1][r]);
            }
            
            for (int r = 0; r < numOfLocations; r++) {
                for (int c = 0; c <= numOfLocations; c++) {
                    System.out.format("%11d",table[r][c]);
                }
                System.out.println();
            }
            
            // trace back to find solution
            System.out.println("Solution:");
            printSol(locations, table, numOfLocations-1, numOfLocations);
            System.out.println();
        }
    } // main
    
    static void printSol(Spot[] locs, int[][] t, int curRow, int curCol) {
        if ((curRow == 0) && (t[curRow][curCol] > 0)) System.out.format("%10.1f",locations[curRow].getDistance());
        else if ((curRow > 0) && (curCol >= 0) && (t[curRow][curCol] > 0)) {
            if (t[curRow][curCol] == locs[curRow].getValue() + t[curRow-1][curRow]) {
                printSol(locs,t,curRow-1,curRow);
                System.out.format("%10.1f",locations[curRow].getDistance());
            }
            else printSol(locs,t,curRow-1,curCol);
        }
    } //printSol(Spot[], int[][], int, int)
    
    
    static Spot[] HeapSort(Spot[] locs) {
        int len = locs.length;
        //double flagVal = chooseFlag(locs);
        locs = heapify(locs);
        Spot[] sorted = new Spot[len];
        for (int i = 0; i < len; i++)
            sorted[i] = extractMin(locs);
        return sorted;
    } // Heapsort(Spot[])
    
    
    static Spot[] heapify(Spot[] locs){
        for (int i = 1; i < locs.length; i++) {
                int temp = i;
                int tempParent = (temp - 1) / 2;
                while ((temp > 0) && (locs[temp].getDistance() < locs[tempParent].getDistance())) {
                    swap(locs, temp, tempParent);
                    temp = tempParent;
                    tempParent = (temp - 1) / 2;
                } // while
        } // for
        return locs;
    } // heapify(Spot[])
    
    static void swap(Spot[] locs, int a, int b){
            Spot t = locs[a];
            locs[a] = locs[b];
            locs[b] = t;
    } // swap(Spot[], int,int)
    
    static Spot extractMin(Spot[] locs){
        Spot returnVal = locs[0];
        promote(locs, 0);    
        return returnVal;
    } // extractMin(Spot[])
    
    static void promote(Spot[] locs, int c) {
        /* 
         * This can be done iteratively, but I'm doing it recursively just for the joy of it
         * 
         * Chooses the smaller of c's children, moves it up to position c, then recurses on the
         * promoted child's position
         */
        
        int n = locs.length;
        
        if (c > n-1) return; // we have fallen off the bottom of the tree
        if (locs[c] == null) return; // we have reached an empty node
        
        if (2*c + 1 > n - 1) { //this node is too close to the bottom of the tree to have children
            locs[c] = null; // mark this node as empty and do nothing more
        }
        else { // at least one child is possible, so examine them and choose the smaller one
            Spot leftChild = locs[2*c + 1];
            Spot rightChild = null;
            if (2*c + 2 < n) rightChild = locs[2*c + 2];
            // leftChild and rightChild now contain pointers if there are children,
            // and each contains null if the corresponding child is empty or non-existent
            
            if (rightChild == null) {
                locs[c] = leftChild;
                promote(locs, 2*c + 1);
            }
            else if (leftChild == null) {
                locs[c] = rightChild;
                promote(locs, 2*c + 2);
            }
            else if (leftChild.getDistance() <= rightChild.getDistance()) {
                locs[c] = leftChild;
                promote(locs, 2*c + 1);
            }
            else {
                locs[c] = rightChild;
                promote(locs, 2*c + 2);
            }
        }
    } // promote(Spot[],int)
    
} // BillBoards class