import java.io.*; import java.util.*; public class Main { public static class pair { int i ; int j ; String psf; pair(int i , int j , String psf){ this.i = i; this.j = j; this.psf = psf; } } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int size = Integer.parseInt(br.readLine()); int[] val = new int[size]; String str1 = br.readLine(); for (int i = 0; i < size; i++) { val[i] = Integer.parseInt(str1.split(" ")[i]); } int[] wts = new int[size]; String str2 = br.readLine(); for (int i = 0; i < size; i++) { wts[i] = Integer.parseInt(str2.split(" ")[i]); } int cap = Integer.parseInt(br.readLine()); //rows will be wts-val and cols will 0 to knapsack capacity (W) int dp[][] = new int[size+1][cap+1]; int m = dp.length , n = dp[0].length; //first row and first col will be 0 by default //rest of the array for(int i = 1 ; i <m ;i++ ){ for(int j = 1 ; j < n;j++){ int plays = 0; int notplays = dp[i-1][j]; if(j >= wts[i-1]) plays = val[i-1] + dp[i-1][j- wts[i-1]]; dp[i][j] = Math.max(plays , notplays); } } System.out.println(dp[m-1][n-1]); BFS(dp,val , wts); } public static void BFS(int[][]dp ,int[] val, int[] wts){ ArrayDeque<pair> q = new ArrayDeque<>(); q.add(new pair(dp.length -1 , dp[0].length-1,"")); while(q.size()>0){ pair rem = q.removeFirst(); int i = rem.i , j = rem.j; String psf = rem.psf; //if players or balls become 0 print psf if(i == 0 || j == 0) System.out.println(psf); else{ //when the number plays and when it doesn't play int plays = 0 , notplays = dp[i-1][j]; if(j >= wts[i-1]) plays= dp[i-1][j-wts[i-1]] + val[i-1]; if(plays == dp[i][j]) q.add(new pair(i-1 , j-wts[i-1] , i-1 +" "+psf)); if(notplays == dp[i][j]) q.add(new pair(i-1 , j , psf)); } } } }