Weakest Garrison Rows

A fortress is described by a binary matrix mat, one row per garrison. In every row all the 1s (soldiers) come before all the 0s (empty posts). Row i is weaker than row j if it has fewer soldiers, or the same number of soldiers and i < j.

Return the indices of the k weakest rows, ordered from weakest to strongest.

Examples

Input:  mat = [[1,1,0,0],
               [1,1,1,1],
               [1,0,0,0],
               [1,1,0,0],
               [1,1,1,0]], k = 3
Output: [2, 0, 3]
Explanation: soldier counts are [2, 4, 1, 2, 3]. Row 2 has 1 soldier, then rows 0 and 3 tie
             with 2 soldiers and the smaller index comes first.

Input:  mat = [[1,1],[0,0]], k = 1
Output: [1]

Constraints

• 1 <= len(mat) <= 5000, 1 <= len(mat[0]) <= 100, all rows have the same length
• 1 <= k <= len(mat)
• Target complexity: O(m * n + m log k) where m is the number of rows.

Goals

• Rank rows by a computed strength with a tie-break on index
• Use tuple ordering so ties resolve automatically
• Extract the k best entries with a heap helper