Night Market Assignment Problem

Night Market Assignment Problem — ExecCode Hard DSA Practice

Solve the Night Market Assignment problem on ExecCode. Free online hard DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Problem Statement There are N stalls and N lanes. Put each stall in exactly one lane. Each lane gets exactly one stall. cost[i][j] is the cost of stall i in lane j. -1 means that pair is not allowed. Print the minimum total cost. If no assignment exists, print -1. The first row is stall 0. Input Format There are N rows after N. Each row has N integers. Output Format One integer. Constraints Use 64-bit integers. Example 1 Input Two stalls. Two lanes. One pairing is 1 + 4. The other is 2 + 3. Both totals are 5. Output Example 2 Input Stall 0 cannot use lane 0, so it takes lane 1 (cost 5). Stall 1 takes lane 0 (cost 2). Total 7. Output Example 3 Input Both stalls can only use lane 1. No assignment exists. Output

Examples

Input 2 1 2 3 4; Output 5. Input 2 -1 5 2 3; Output 7. Input 2 -1 5 -1 3; Output -1

Constraints

1 ≤ N ≤ 40, -1 ≤ cost[i][j] ≤ 1e9.

Practice Night Market Assignment free on ExecCode. Browse DSA problems, topic map, and placement guides.