Problem Statement

A ride-hailing company is rearranging its server systems to reduce latency. Resources are currently distributed across n data centers and must be consolidated into at most k data centers. The cost of migrating all services from data center i to data center j is migrationCost[i][j] . Determine the minimum total migration cost required to achieve this consolidation. Notes Data centers are numbered from 0 to n − 1 . Services can be migrated indirectly through intermediate data centers, paying the sum of the hops. After consolidation, no more than k data centers should contain services. The cost matrix need not be symmetric. Input Format The first line contains two integers n and k . Each of the next n lines contains n space-separated integers; the j -th value on the i -th line is migrationCost[i][j] . Output Format Print a single integer — the minimum possible total cost. Constraints 1 ≤ n ≤ 18 1 ≤ k ≤ n 0 ≤ migrationCost[i][j] ≤ 10 5 migrationCost[i][i] = 0