class Solution {
public:
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        const int INF = 1e8;
        vector<vector<vector<int>>> f(m, vector<vector<int>>(target + 1, vector<int>(n + 1, INF)));

        if (houses[0]) {
            f[0][1][houses[0]] = 0;
        } else {
            for (int i = 1; i <= n; ++i) {
                f[0][1][i] = cost[0][i - 1];
            }
        }

        for (int i = 1; i < m; ++i) {
            int k = houses[i];
            for (int j = 1; j <= target; ++j) {
                if(k) {
                    for (int t = 1; t <= n; ++t) {
                        if (t == k) {
                            f[i][j][k] = min(f[i][j][k], f[i - 1][j][t]);
                        } else {
                            f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][t]);
                        }
                    }
                } else {
                    for (int k = 1; k <= n; ++k) {
                        for (int t = 1; t <= n; ++t) {
                            if (t == k) {
                                f[i][j][k] = min(f[i][j][k], f[i - 1][j][t] + cost[i][k - 1]);
                            } else {
                                f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][t] + cost[i][k - 1]);
                            }
                        }
                    }
                }
            }
        }

        int res = INF;
        for (int i = 1; i <= n; ++i) {
            res = min(res, f[m - 1][target][i]);
        }
        if (res == INF) {
            return -1;
        } 
        return res;
    }
};