#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INF = (1LL << 60); // A very large number (safe for sums up to ~1e18)

// ===================================================================
// This file contains a collection of algorithms to solve the 
// "Assignment Problem" (and related matching problems). 
// 
// The main workhorse here is the Hungarian Algorithm (also called 
// Kuhn-Munkres algorithm). 
// 
// Each function is ready to be used as a "black box". 
// Read the comments above each one to understand:
//   - What it solves
//   - What input it expects
//   - What it returns
//   - Time complexity
//   - Important constraints / assumptions
// 
// Technical terms explained simply:
//   - "Assignment Problem": You have N workers and M jobs. 
//     Each worker must be assigned to exactly one job (and each job 
//     to at most one worker). You want the total cost to be minimum.
//   - "Bipartite Graph": A graph with two sets of nodes (Left side = workers, 
//     Right side = jobs). Edges only go from Left to Right.
//   - "Matching": A set of edges where no two edges share a node.
//     (e.g., each worker gets a unique job).
//   - "Potentials" (u, v): Internal numbers used by the Hungarian 
//     algorithm to guide the search. You don't need to understand them 
//     to use the functions.
//   - "Bitmask DP": Dynamic Programming where a "bitmask" (an integer 
//     like 1011) represents a set of jobs that have been taken.
// ===================================================================

// ===================================================================
// 1) Hungarian Algorithm (Square Matrix) - Minimum Cost
//    This is the standard O(n^3) algorithm.
//    It finds the optimal assignment for a square cost matrix.
// ===================================================================

// 1.1) Solve the assignment problem for a square matrix.
//      Parameters:
//        - cost: a 2D vector of size n x n. 
//                cost[i][j] = cost of assigning worker i to job j.
//      Returns:
//        - a pair <total_cost, assignment>.
//          - total_cost (long long): the minimum total cost.
//          - assignment (vector<int>): a vector of size n.
//            assignment[i] = j means worker i is assigned to job j.
//            (Indices are 0-based).
//      Time complexity: O(n^3), where n = number of rows = number of cols.
//      Constraints:
//        - Matrix must be square (n rows, n columns).
//        - Costs can be negative, zero, or positive.
//        - n should be >= 1. If n == 0, returns {0, {}}.
//      Note: 
//        - This function uses internal arrays "u", "v", "p", "way".
//          You do NOT need to understand these to use the function.
//        - The algorithm guarantees the optimal assignment.
pair<ll, vector<int>> hungarianMinCost(const vector<vector<ll>>& cost) {
    int n = (int)cost.size();
    if (n == 0) return {0, {}};
    
    // Internal variables (do not worry about their meaning)
    vector<ll> u(n + 1), v(n + 1);
    vector<int> p(n + 1), way(n + 1);
    
    for (int i = 1; i <= n; i++) {
        p[0] = i;
        int j0 = 0;
        vector<ll> minv(n + 1, INF);
        vector<char> used(n + 1, false);
        do {
            used[j0] = true;
            int i0 = p[j0];
            ll delta = INF;
            int j1 = 0;
            for (int j = 1; j <= n; j++) {
                if (!used[j]) {
                    ll cur = cost[i0 - 1][j - 1] - u[i0] - v[j];
                    if (cur < minv[j]) {
                        minv[j] = cur;
                        way[j] = j0;
                    }
                    if (minv[j] < delta) {
                        delta = minv[j];
                        j1 = j;
                    }
                }
            }
            for (int j = 0; j <= n; j++) {
                if (used[j]) {
                    u[p[j]] += delta;
                    v[j] -= delta;
                } else {
                    minv[j] -= delta;
                }
            }
            j0 = j1;
        } while (p[j0] != 0);
        
        do {
            int j1 = way[j0];
            p[j0] = p[j1];
            j0 = j1;
        } while (j0);
    }
    
    vector<int> assignment(n);
    for (int j = 1; j <= n; j++) {
        if (p[j] > 0) {
            assignment[p[j] - 1] = j - 1;
        }
    }
    ll totalCost = -v[0]; // The total minimum cost
    return {totalCost, assignment};
}

// ===================================================================
// 2) Hungarian Algorithm (Square Matrix) - Maximum Cost
//    To maximize the total cost, we just negate all costs and run 
//    the minimum cost version.
// ===================================================================

// 2.1) Solve the assignment problem for a square matrix to MAXIMIZE cost.
//      Parameters:
//        - cost: a 2D vector of size n x n (the profit matrix).
//      Returns:
//        - a pair <max_profit, assignment>.
//          - max_profit (long long): the maximum total profit.
//          - assignment (vector<int>): optimal assignment.
//      Time complexity: O(n^3).
//      Constraints: Same as min cost version (square matrix).
//      Note: 
//        - Internally, it multiplies costs by -1 and calls the min-cost 
//          Hungarian. So if costs are up to 1e9, the negated values are 
//          safe within 64-bit.
pair<ll, vector<int>> hungarianMaxCost(const vector<vector<ll>>& cost) {
    int n = (int)cost.size();
    vector<vector<ll>> negCost(n, vector<ll>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            negCost[i][j] = -cost[i][j];
        }
    }
    auto res = hungarianMinCost(negCost);
    return {-res.first, res.second}; // Negate the total cost back to positive
}

// ===================================================================
// 3) Hungarian Algorithm (Rectangular Matrix) - Minimum Cost
//    In many problems, we have N workers and M jobs, where N <= M.
//    We only need to assign each worker to a unique job.
//    This function handles that case in O(N^2 * M).
// ===================================================================

// 3.1) Solve assignment for rectangular matrix (N rows, M cols) with N <= M.
//      Parameters:
//        - cost: a 2D vector of size n x m. (n = rows, m = cols).
//                Assumes n <= m (more jobs than workers).
//      Returns:
//        - a pair <total_cost, assignment>.
//          - total_cost (ll): minimum cost to assign every row to a unique column.
//          - assignment (vector<int>): size n. assignment[i] = j.
//      Time complexity: O(n^2 * m). 
//      Constraints:
//        - n <= m (we cannot assign more workers than jobs).
//        - If n > m, swap rows/cols (or transpose the matrix) before calling.
//        - Costs can be negative.
//      Note:
//        - This is the standard CP-algorithms implementation adapted for 
//          rectangular matrices. 
//        - If you have more workers than jobs (n > m), you can call 
//          hungarianMinCostRectangularTransposed (provided below).
pair<ll, vector<int>> hungarianMinCostRectangular(const vector<vector<ll>>& cost) {
    int n = (int)cost.size();    // rows (workers)
    int m = (int)cost[0].size(); // cols (jobs)
    if (n > m) {
        // If workers > jobs, we cannot assign everyone.
        // You must handle this case separately (e.g., add dummy jobs).
        // This implementation assumes n <= m.
        throw invalid_argument("Number of rows must be <= number of columns.");
    }
    
    vector<ll> u(n + 1), v(m + 1);
    vector<int> p(m + 1), way(m + 1);
    
    for (int i = 1; i <= n; i++) {
        p[0] = i;
        int j0 = 0;
        vector<ll> minv(m + 1, INF);
        vector<char> used(m + 1, false);
        do {
            used[j0] = true;
            int i0 = p[j0];
            ll delta = INF;
            int j1 = 0;
            for (int j = 1; j <= m; j++) {
                if (!used[j]) {
                    ll cur = cost[i0 - 1][j - 1] - u[i0] - v[j];
                    if (cur < minv[j]) {
                        minv[j] = cur;
                        way[j] = j0;
                    }
                    if (minv[j] < delta) {
                        delta = minv[j];
                        j1 = j;
                    }
                }
            }
            for (int j = 0; j <= m; j++) {
                if (used[j]) {
                    u[p[j]] += delta;
                    v[j] -= delta;
                } else {
                    minv[j] -= delta;
                }
            }
            j0 = j1;
        } while (p[j0] != 0);
        
        do {
            int j1 = way[j0];
            p[j0] = p[j1];
            j0 = j1;
        } while (j0);
    }
    
    vector<int> assignment(n);
    for (int j = 1; j <= m; j++) {
        if (p[j] > 0 && p[j] <= n) {
            assignment[p[j] - 1] = j - 1;
        }
    }
    ll totalCost = -v[0];
    return {totalCost, assignment};
}

// 3.2) Helper to handle the case where rows > cols (more workers than jobs).
//      Parameters:
//        - cost: n x m matrix where n > m.
//      Returns: same as 3.1.
//      How it works: 
//        - It transposes the matrix (swaps rows and columns) so that the 
//          number of rows becomes the smaller dimension, then calls 3.1.
//        - Then it translates the assignment back to the original order.
//      Time complexity: O(m^2 * n).
pair<ll, vector<int>> hungarianMinCostRectangularTransposed(const vector<vector<ll>>& cost) {
    int n = (int)cost.size();    // rows
    int m = (int)cost[0].size(); // cols
    if (n <= m) {
        // If already n <= m, just call the normal one.
        return hungarianMinCostRectangular(cost);
    }
    // Transpose: new matrix has size m x n
    vector<vector<ll>> transCost(m, vector<ll>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            transCost[j][i] = cost[i][j];
        }
    }
    auto res = hungarianMinCostRectangular(transCost); // res.assignment is of size m
    // Now we need to map back.
    // transCost assignment: transAssignment[row_j] = col_i.
    // This means original job 'row_j' is assigned to original worker 'col_i'.
    vector<int> originalAssignment(n, -1);
    for (int j = 0; j < m; j++) {
        int worker = res.second[j];
        originalAssignment[worker] = j;
    }
    return {res.first, originalAssignment};
}

// 3.3) Maximum Cost version for Rectangular matrices.
//      Same logic: negate costs and call the min-cost version.
pair<ll, vector<int>> hungarianMaxCostRectangular(const vector<vector<ll>>& cost) {
    int n = (int)cost.size();
    int m = (int)cost[0].size();
    vector<vector<ll>> negCost(n, vector<ll>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            negCost[i][j] = -cost[i][j];
        }
    }
    auto res = hungarianMinCostRectangular(negCost); // handles n <= m
    return {-res.first, res.second};
}

// ===================================================================
// 4) Bitmask DP (Dynamic Programming) for Assignment 
//    This is the "easy" way to solve assignment when N (or M) is small.
//    It is VERY common in ECPC/ACPC when N <= 20.
//    It is not as fast as Hungarian for N=1000, but it is much easier 
//    to modify for extra constraints (like "must pick exactly K items").
// ===================================================================

// 4.1) Assignment using Bitmask DP (Minimum Cost).
//      Parameters:
//        - cost: n x m matrix. 
//        - We assign workers (rows) to jobs (cols) one by one.
//        - n is the number of workers.
//        - m is the number of jobs. (Usually n <= m, but if n > m, we can 
//          flip the loops or handle it).
//      Returns:
//        - minimum total cost to assign all workers to unique jobs.
//        - If impossible (n > m), returns INF.
//      Time complexity: O(n * 2^m) or O(m * 2^n). 
//        - Choose the smaller dimension for the bitmask to be efficient.
//      Constraints:
//        - The dimension used for the bitmask (which is the number of jobs 
//          or workers) must be <= 20 (or 22 with optimization).
//        - Works with negative costs.
//      Note: 
//        - This returns ONLY the total cost, not the assignment.
//        - If you need the assignment, you can store the "parent" choice 
//          in a separate array.
//        - This is a "black box" for small N only.
ll assignmentBitmaskDP(const vector<vector<ll>>& cost) {
    int n = (int)cost.size(); // workers
    int m = (int)cost[0].size(); // jobs
    
    if (n > m) return INF; // Not enough jobs for all workers.
    
    // DP over subsets of jobs.
    // dp[mask] = minimum cost to assign the first k workers 
    // (where k = number of set bits in mask) to the jobs in mask.
    vector<ll> dp(1 << m, INF);
    dp[0] = 0;
    
    for (int mask = 0; mask < (1 << m); mask++) {
        int worker = __builtin_popcount(mask); // how many workers assigned so far
        if (worker == n) continue; // all workers assigned
        
        for (int j = 0; j < m; j++) {
            if (!(mask & (1 << j))) {
                int newMask = mask | (1 << j);
                dp[newMask] = min(dp[newMask], dp[mask] + cost[worker][j]);
            }
        }
    }
    
    ll ans = INF;
    for (int mask = 0; mask < (1 << m); mask++) {
        if (__builtin_popcount(mask) == n) {
            ans = min(ans, dp[mask]);
        }
    }
    return ans;
}

// 4.2) Assignment Bitmask DP (Maximum Cost).
//      Just negate the costs inside.
ll assignmentBitmaskMaxDP(const vector<vector<ll>>& cost) {
    int n = (int)cost.size();
    int m = (int)cost[0].size();
    vector<vector<ll>> negCost(n, vector<ll>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            negCost[i][j] = -cost[i][j];
        }
    }
    return -assignmentBitmaskDP(negCost);
}

// ===================================================================
// 5) Kuhn's Algorithm (Maximum Bipartite Matching)
//    This finds the maximum number of pairs we can match in a 
//    bipartite graph. 
//    It is used as a helper for the "Minimize Maximum Cost" trick.
// ===================================================================

// 5.1) Kuhn's Algorithm (DFS-based) to find maximum matching.
//      Parameters:
//        - adj: adjacency list of the left side (size n).
//               adj[i] contains the list of right-side nodes (0-based) 
//               that left node i can connect to.
//        - n: number of nodes on the left.
//        - m: number of nodes on the right.
//      Returns:
//        - The maximum number of edges in the matching.
//      Time complexity: O(n * E) where E is the total number of edges.
//        - In practice, very fast for sparse graphs.
//      Constraints:
//        - Works for any bipartite graph.
//        - If you have both sides <= 500, it runs fine.
//      Note:
//        - This function does NOT return the actual matching edges, 
//          only the count. (You can modify it to return the matching array 
//          if needed, but for the binary-search trick below, we only 
//          need the count).
int kuhnMatchingCount(const vector<vector<int>>& adj, int n, int m) {
    vector<int> matchR(m, -1); // matchR[j] = which left node is matched to right j
    vector<int> visited;
    
    function<bool(int)> dfs = [&](int u) {
        for (int v : adj[u]) {
            if (visited[v]) continue;
            visited[v] = 1;
            if (matchR[v] == -1 || dfs(matchR[v])) {
                matchR[v] = u;
                return true;
            }
        }
        return false;
    };
    
    int matching = 0;
    for (int u = 0; u < n; u++) {
        visited.assign(m, 0);
        if (dfs(u)) matching++;
    }
    return matching;
}

// ===================================================================
// 6) Advanced Trick: Minimize the Maximum Cost (Minimax Assignment)
//    Problem: We want to assign every worker to a unique job, but we 
//    want the maximum cost among all selected edges to be as small 
//    as possible (instead of minimizing the sum).
//    This is solved by Binary Search on the answer + Kuhn Matching.
// ===================================================================

// 6.1) Check if we can assign all workers with every edge cost <= limit.
//      Parameters:
//        - cost: n x m matrix (n <= m).
//        - limit: the maximum allowed cost for any chosen edge.
//      Returns:
//        - true if a perfect matching exists using only edges with cost <= limit.
//      Time complexity: O(n * E) for each call.
//      Note:
//        - This is a feasibility check used inside binary search.
bool canAssignWithMaxCost(const vector<vector<ll>>& cost, ll limit) {
    int n = (int)cost.size();
    int m = (int)cost[0].size();
    if (n > m) return false; // cannot assign more workers than jobs.
    
    vector<vector<int>> adj(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (cost[i][j] <= limit) {
                adj[i].push_back(j);
            }
        }
    }
    int maxMatch = kuhnMatchingCount(adj, n, m);
    return maxMatch == n; // we matched every worker
}

// 6.2) Find the minimum possible maximum cost.
//      Parameters:
//        - cost: n x m matrix.
//      Returns:
//        - The minimum value X such that we can assign all workers using 
//          only edges with cost <= X.
//      Time complexity: O(log(range) * n * E).
//      Constraints:
//        - Costs can be negative. We handle that by taking the min/max 
//          of the matrix as the binary search bounds.
//        - Assumes at least one valid assignment exists (if not, returns INF).
ll minMaxAssignmentCost(const vector<vector<ll>>& cost) {
    int n = (int)cost.size();
    int m = (int)cost[0].size();
    if (n > m) return INF;
    
    ll low = INF, high = -INF;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            low = min(low, cost[i][j]);
            high = max(high, cost[i][j]);
        }
    }
    
    // If n == 0, return 0.
    if (n == 0) return 0;
    
    ll ans = high;
    while (low <= high) {
        ll mid = low + (high - low) / 2;
        if (canAssignWithMaxCost(cost, mid)) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return ans;
}

// ===================================================================
// 7) TRICKS & EXTRA PATTERNS (FULLY IMPLEMENTED FUNCTIONS)
//    These are the actual standalone functions for the common 
//    assignment‑problem variations that appear in ECPC / ACPC.
// ===================================================================

// ===================================================================
// 7.1) Convert any rectangular matrix into a SQUARE matrix by adding 
//      dummy rows or columns with cost ZERO.
//      This lets you use the standard square Hungarian algorithm 
//      (hungarianMinCost) even when N != M.
// ===================================================================

// PURPOSE:
//   Takes an N x M cost matrix and returns a square matrix (size K x K)
//   where K = max(N, M). 
//   - If N > M, it adds (N - M) dummy columns (jobs) with cost 0.
//   - If M > N, it adds (M - N) dummy rows (workers) with cost 0.
//   - If N == M, it returns a copy of the original.
//
// INPUT:
//   cost : a 2D vector (N rows, M columns) of long long.
//
// OUTPUT:
//   Returns a square vector<vector<ll>> of size K x K.
//   Dummy rows/columns are placed at the end.
//
// TIME COMPLEXITY:
//   O(N * M) to copy the original, plus O(K^2) overall.
//
// CONSTRAINTS / PRECONDITIONS:
//   - None. Works for any N, M >= 0.
//   - Costs can be negative, zero, or positive.
//
// NOTES:
//   - After getting the square matrix, you can call 
//     `hungarianMinCost(squareMatrix)` to get the optimal assignment.
//   - If the original matrix had more rows (workers) than columns (jobs),
//     adding dummy jobs (cost 0) means that extra workers will be 
//     assigned to dummy jobs, i.e., they do no real work.
//   - If the original had more columns (jobs) than rows (workers),
//     adding dummy workers (cost 0) means that extra jobs will be 
//     assigned to dummy workers, i.e., they remain unassigned.
vector<vector<ll>> makeSquareMatrixForAssignment(const vector<vector<ll>>& cost) {
    int n = (int)cost.size();
    if (n == 0) return {}; // empty matrix
    int m = (int)cost[0].size();
    
    int k = max(n, m);
    vector<vector<ll>> sq(k, vector<ll>(k, 0));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            sq[i][j] = cost[i][j];
        }
    }
    // The remaining entries are already 0 (dummy rows/columns).
    return sq;
}

// ===================================================================
// 7.2) Assignment where you are ALLOWED to leave some workers 
//      unassigned, but you pay a fixed PENALTY for each unassigned worker.
//      This is extremely common in contest problems.
// ===================================================================

// PURPOSE:
//   Solves the assignment problem for N workers and M jobs.
//   Each worker must be assigned to at most ONE job.
//   If a worker is NOT assigned to any real job, you pay a fixed 
//   penalty `penalty` for that worker.
//   The goal is to minimize (total assignment cost + total penalties).
//
// INPUT:
//   cost    : N x M matrix (long long). cost[i][j] is the cost of 
//             assigning worker i to job j.
//   penalty : a long long value (the cost per unassigned worker).
//             Can be negative (if you really don't want to assign someone),
//             but usually it is a positive number.
//
// OUTPUT:
//   Returns a pair <total_cost, assignment>.
//   - total_cost (long long): the minimum total cost (assignment + penalties).
//   - assignment (vector<int>): size N. 
//       assignment[i] = j (where 0 <= j < M) means worker i is assigned 
//                        to real job j.
//       assignment[i] = M + k (where k >= 0) means worker i is assigned 
//                        to a dummy job, i.e., worker i is unassigned.
//
// TIME COMPLEXITY:
//   O(N^2 * (M + N)) if you use the rectangular Hungarian, 
//   but typically you will use hungarianMinCostRectangular which is 
//   O(N^2 * M') where M' = M + N.
//
// CONSTRAINTS / PRECONDITIONS:
//   - The number of real jobs M can be less than, equal to, or greater 
//     than N. The function creates dummy jobs so that there are always 
//     enough jobs for every worker.
//   - All costs must fit in long long.
//   - The returned assignment indices >= M indicate unassigned workers.
//
// NOTES:
//   - Internally, it creates a new matrix of size N x (M + N). 
//     The last N columns are dummy jobs, all having cost = penalty.
//     It then calls hungarianMinCostRectangular on this matrix.
//   - If you just want to allow unassigned workers without penalty, 
//     set penalty = 0.
pair<ll, vector<int>> assignmentWithUnassignedPenalty(
    const vector<vector<ll>>& cost,
    ll penalty
) {
    int n = (int)cost.size();    // workers
    int m = (int)cost[0].size(); // real jobs
    
    // New matrix: n workers, (m + n) jobs (n dummy jobs)
    vector<vector<ll>> newCost(n, vector<ll>(m + n));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            newCost[i][j] = cost[i][j];
        }
        for (int j = m; j < m + n; j++) {
            newCost[i][j] = penalty; // dummy job cost = penalty
        }
    }
    
    // Use the rectangular Hungarian (n rows, m+n columns, and n <= m+n)
    auto res = hungarianMinCostRectangular(newCost);
    return res; // assignment indices go up to m+n-1
}

// ===================================================================
// 7.3) Count the number of perfect matchings (total number of ways 
//      to assign all workers to unique jobs) using Bitmask DP.
//      This is useful when the number of jobs (or workers) is small 
//      (typically <= 20).
// ===================================================================

// PURPOSE:
//   Given an N x M matrix indicating which edges are allowed, 
//   count how many ways we can assign every worker (0..N-1) to a 
//   distinct job (0..M-1) using only allowed edges.
//   Every worker must get exactly one job, and no two workers share a job.
//
// INPUT:
//   allowed : N x M matrix of integers (or booleans).
//             allowed[i][j] = 1 (or true) means worker i CAN take job j.
//             allowed[i][j] = 0 (or false) means it is forbidden.
//
// OUTPUT:
//   Returns a long long integer: the total number of valid assignments.
//   If N > M, returns 0 immediately (not enough jobs).
//   If the count exceeds 2^63 - 1, it will overflow; use __int128 
//   if you need bigger numbers, but that is rare for N <= 20.
//
// TIME COMPLEXITY:
//   O(N * 2^M) where M is the number of columns (jobs).
//   Therefore, M must be small (<= 20 for typical time limits).
//
// CONSTRAINTS / PRECONDITIONS:
//   - M (number of jobs) should be <= 20 (or 22 with optimizations).
//   - N <= M, otherwise 0 is returned.
//   - Works for any allowed matrix (no need for costs).
//
// NOTES:
//   - This uses the standard subset DP: dp[mask] stores the number of 
//     ways to assign the first `popcount(mask)` workers to the jobs 
//     represented by `mask`.
//   - If you need to count matchings where not all workers must be assigned,
//     you can sum dp[mask] over all masks (but this function counts 
//     perfect matchings only, i.e., all N workers assigned).
long long countPerfectMatchings(const vector<vector<int>>& allowed) {
    int n = (int)allowed.size();    // workers
    if (n == 0) return 1;           // empty case
    int m = (int)allowed[0].size(); // jobs
    
    if (n > m) return 0; // cannot assign all workers
    
    vector<long long> dp(1 << m, 0);
    dp[0] = 1;
    
    for (int mask = 0; mask < (1 << m); mask++) {
        int worker = __builtin_popcount(mask); // how many workers assigned so far
        if (worker == n) continue; // all workers are already assigned
        
        for (int j = 0; j < m; j++) {
            if (mask & (1 << j)) continue; // job j already taken
            if (!allowed[worker][j]) continue; // edge is forbidden
            
            int newMask = mask | (1 << j);
            dp[newMask] += dp[mask];
        }
    }
    
    long long ans = 0;
    for (int mask = 0; mask < (1 << m); mask++) {
        if (__builtin_popcount(mask) == n) {
            ans += dp[mask];
        }
    }
    return ans;
}

// ===================================================================
// 7.4) Minimum cost assignment with FORBIDDEN edges.
//      Some edges (i, j) are not allowed to be chosen.
//      This function builds the cost matrix by setting forbidden 
//      edges to INF, runs the Hungarian algorithm, and returns the result.
//      If no complete assignment exists, it returns INF and an empty 
//      assignment vector.
// ===================================================================

// PURPOSE:
//   Solves the assignment problem (N workers, M jobs, N <= M) where 
//   certain edges are FORBIDDEN (cannot be used). 
//   It returns the minimum total cost using only allowed edges, 
//   or signals impossibility if no perfect assignment exists.
//
// INPUT:
//   cost    : N x M matrix (long long) containing the regular costs.
//   allowed : N x M matrix of integers (or booleans).
//             allowed[i][j] = 1 (or true)  -> edge is allowed.
//             allowed[i][j] = 0 (or false) -> edge is forbidden.
//
// OUTPUT:
//   Returns a pair <total_cost, assignment>.
//   - If a valid assignment exists:
//       total_cost is the minimum cost.
//       assignment is a vector of size N (assignment[i] = j).
//   - If NO valid assignment exists (because forbidden edges block it):
//       total_cost = INF (the global constant).
//       assignment is an empty vector ({}).
//
// TIME COMPLEXITY:
//   O(N^2 * M) (calls the rectangular Hungarian internally).
//
// CONSTRAINTS / PRECONDITIONS:
//   - The input matrix must have N <= M (otherwise impossible to assign 
//     all workers – returns {INF, {}}).
//   - Costs can be negative, zero, or positive.
//   - The INF constant is defined globally (usually 4e18 or (1LL<<60)).
//   - The total cost of a valid assignment must be < INF/2 to be 
//     considered valid.
//
// NOTES:
//   - Internally, it builds a new matrix where forbidden edges are 
//     replaced with INF (a very large number). 
//   - It then calls `hungarianMinCostRectangular`. 
//   - If the returned cost is >= INF/2, we conclude that no feasible 
//     assignment exists.
pair<ll, vector<int>> assignmentWithForbiddenEdges(
    const vector<vector<ll>>& cost,
    const vector<vector<int>>& allowed
) {
    int n = (int)cost.size();
    if (n == 0) return {0, {}};
    int m = (int)cost[0].size();
    
    if (n > m) {
        return {INF, {}}; // not enough jobs for all workers
    }
    
    vector<vector<ll>> modifiedCost = cost;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!allowed[i][j]) {
                modifiedCost[i][j] = INF; // forbid this edge
            }
        }
    }
    
    auto res = hungarianMinCostRectangular(modifiedCost);
    
    // If the total cost is too large, it means the algorithm was forced 
    // to pick at least one forbidden edge (or the problem is infeasible).
    if (res.first >= INF / 2) {
        return {INF, {}};
    }
    return res;
}

// ===================================================================
// End of Section 7 functions.
// ===================================================================

// ===================================================================
// main() with example usage (you can ignore this part)
// ===================================================================

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Example 1: Square matrix min cost
    vector<vector<ll>> cost1 = {
        {4, 1, 3},
        {2, 0, 5},
        {3, 2, 2}
    };
    auto res1_min = hungarianMinCost(cost1);
    cout << "Min Cost: " << res1_min.first << "\n";
    cout << "Assignment: ";
    for (int x : res1_min.second) cout << x << " ";
    cout << "\n";

    // Example 2: Rectangular matrix (3 workers, 5 jobs)
    vector<vector<ll>> cost2 = {
        {1, 2, 3, 4, 5},
        {5, 4, 3, 2, 1},
        {2, 3, 4, 5, 6}
    };
    auto res2_rect = hungarianMinCostRectangular(cost2);
    cout << "Rect Min Cost: " << res2_rect.first << "\n";

    // Example 3: Minimize Maximum Cost
    vector<vector<ll>> cost3 = {
        {1, 100, 100},
        {100, 1, 100},
        {100, 100, 1}
    };
    cout << "Min Max Cost: " << minMaxAssignmentCost(cost3) << "\n"; // Output: 1

    // Example 4: Bitmask DP (small N)
    vector<vector<ll>> cost4 = {
        {10, 20, 30},
        {40, 50, 60},
        {70, 80, 90}
    };
    cout << "Bitmask DP Min: " << assignmentBitmaskDP(cost4) << "\n";
    
    // Example 5: Penalty for unassigned workers
    vector<vector<ll>> cost5 = {
        {1, 2},
        {3, 4},
        {5, 6} // 3 workers, 2 jobs
    };
    ll penalty = 10;
    auto res5 = assignmentWithUnassignedPenalty(cost5, penalty);
    cout << "With penalty cost: " << res5.first << "\n";
    cout << "Assignment: ";
    for (int x : res5.second) cout << x << " ";
    cout << "\n";

    // Example 6: Make square matrix and use standard square Hungarian
    auto sq = makeSquareMatrixForAssignment(cost5); // 3x3
    auto res6 = hungarianMinCost(sq);
    cout << "Square Hungarian on padded matrix: " << res6.first << "\n";

    // Example 7: Count perfect matchings (only allowed edges)
    vector<vector<int>> allowed = {
        {1, 1},
        {1, 0}, // worker 1 cannot take job 1
        {1, 1}
    };
    long long ways = countPerfectMatchings(allowed);
    cout << "Number of perfect matchings: " << ways << "\n";

    // Example 8: Forbidden edges
    auto res7 = assignmentWithForbiddenEdges(cost5, allowed);
    if (res7.first == INF) {
        cout << "No feasible assignment!\n";
    } else {
        cout << "With forbidden edges, cost: " << res7.first << "\n";
    }

    return 0;
}