class Solution {
    int helper(int[][] costs, int i, int j) {
        if (i + j >= costs.length) {
            return 0;
        }
       
        int minCost = Integer.MAX_VALUE;
        if (i >= costs.length) {
            minCost = costs[i + j][1] + helper(costs, i, j + 1);
        } else if (j >= costs.length / 2) {
            minCost = costs[i + j][0] + helper(costs, i + 1, j);
        } else {
            minCost = Math.min(costs[i + j][0] + helper(costs, i + 1, j),
                           costs[i + j][1] + helper(costs, i, j + 1));
        }
        return minCost;
    }
   
    public int twoCitySchedCost(int[][] costs) {
        return helper(costs, 0, 0);        
    }
}