package leetcode;

public class Solution321 {
    public int maxNumber(int[] nums1, int[] nums2, int k) {
        int m = nums1.length, n = nums2.length;
        int[][][] F = new int[m + 1][n + 1][k + 1];
        
        for (int i = 0; i <= m; i++) {
        	for (int j = 0; j <= n; j++) {
        		for (int c = 1; c <= Math.min(i + j, k); c++) {
        			int maxValue = 0;
        			if (i > 0) {
        				maxValue = Math.max(F[i - 1][j][c - 1] * 10 + nums1[i - 1], maxValue); // pick nums1
        				maxValue = Math.max(F[i - 1][j][c], maxValue); // don't pick nums1
        			}
        			
        			if (j > 0) {
	        			maxValue = Math.max(F[i][j - 1][c - 1] * 10 + nums2[j - 1], maxValue); // pick nums2
	        			maxValue = Math.max(F[i][j - 1][c], maxValue); // don't pick nums2
        			}
        			F[i][j][c] = maxValue;
        		}
        	}
        }
        
        return F[m][n][k];
    }
}