Minimum cost to merge sorted lists

impl Solution {
  pub fn min_merge_cost(lists: Vec<Vec<i32>>) -> i64 {
    let n = lists.len();
    // For each subset of lists, we need to know the merged sorted list's length and median.
    // Length of merged subset = sum of lengths of lists in subset.
    // Median of merged subset = the element at index (total_len - 1) / 2 in the merged sorted array.

    // Precompute for each subset: length and median
    // Since n <= 12 and total elements <= 2000, we can merge lists for each subset.
    // But 2^12 = 4096 subsets, and merging could be expensive. Let's be smart.

    // Actually, we need median for every possible subset that can appear during merging.
    // Any subset can appear. So we need median for all 2^n - 1 non-empty subsets.

    // For each subset, we can compute the merged sorted array and find the median.
    // But that's too expensive for large subsets. Instead, we can precompute medians
    // by building up subsets incrementally.

    // Alternative: for each subset, we know the total length. The median is at position
    // (total_len - 1) / 2. We can find this by iterating through sorted lists using
    // a merge-like approach or by precomputing.

    // Since total elements <= 2000, let's just merge for each subset.
    // Actually 4096 subsets * merge cost... let's think about this differently.

    // We can precompute the merged array for each subset by building up.
    // For single element subsets, it's just the list itself.
    // For larger subsets, pick any element j in the subset, merge subset\{j} with {j}.
    // But storing 4096 arrays of up to 2000 elements = 8M entries, feasible.

    // Actually, let's just precompute median for each subset.
    // For a subset S, we need to find the k-th smallest element where k = (len(S)-1)/2.
    // len(S) = sum of lengths of lists in S.
    // Since each list is sorted, we can find the k-th element using a merge of sorted lists.

    // Simpler approach: precompute for each subset by merging all lists in that subset.
    // We'll do this incrementally: for each subset, merge by adding one list at a time.

    let full = 1usize << n;

    // Precompute lengths
    let lens: Vec<usize> = lists.iter().map(|l| l.len()).collect();
    let mut subset_len = vec![0usize; full];
    for mask in 1..full {
      let bit = mask & mask.wrapping_neg(); // lowest set bit
      let idx = bit.trailing_zeros() as usize;
      subset_len[mask] = subset_len[mask ^ bit] + lens[idx];
    }

    // Precompute merged arrays for each subset
    // To save memory/time, we only need medians, not full arrays.
    // But to compute median we need the merged array (or k-th element).
    // Let's store merged arrays.

    // Actually, with n<=12 and total<=2000, storing all merged arrays is too much memory.
    // Let's compute median for each subset on the fly using a k-th element approach.

    // For k-th element of merge of sorted arrays: binary search or direct merge.
    // Direct merge up to k elements is O(k * number_of_lists) which is O(2000 * 12) per subset.
    // 4096 * 24000 = ~100M ops. Might be tight but doable.

    // Actually let's just merge and store. Max total across all subsets:
    // Each element appears in 2^(n-1) subsets. Total storage = sum_elements * 2^(n-1) = 2000 * 2048 = 4M. Fine.

    // Let's use a different approach: precompute median for each subset using k-way merge up to median position.

    let mut median = vec![0i64; full];

    for mask in 1..full {
      let total_len = subset_len[mask];
      if total_len == 0 { continue; }
      let med_pos = (total_len - 1) / 2;

      // Find the med_pos-th element (0-indexed) in the merge of all lists in mask
      // Use a pointer-based merge approach
      let mut pointers = vec![0usize; n];
      for _ in 0..=med_pos {
        // Find the minimum among current pointers
        let mut min_val = i64::MAX;
        let mut min_idx = 0;
        for j in 0..n {
          if mask & (1 << j) != 0 && pointers[j] < lens[j] {
            let v = lists[j][pointers[j]] as i64;
            if v < min_val {
              min_val = v;
              min_idx = j;
            }
          }
        }
        median[mask] = min_val;
        pointers[min_idx] += 1;
      }
    }

    // DP: dp[mask] = minimum cost to merge all lists in mask into one list
    // For single lists (popcount=1), dp = 0
    // For mask with popcount >= 2, try all ways to split mask into two non-empty subsets
    // dp[mask] = min over all proper non-empty subsets s of mask:
    //   dp[s] + dp[mask^s] + subset_len[mask] + abs(median[s] - median[mask^s])
    // Wait, but the cost is for merging the final two groups. When we merge group s and group mask^s,
    // each is already merged into a single list. The cost of that final merge is:
    //   subset_len[s] + subset_len[mask^s] + abs(median[s] - median[mask^s])
    // But the median of each group is the median of all elements in that group merged.

    // However, there's a subtlety: when we merge within group s, the order of merges affects
    // intermediate costs but NOT the final merged list (it's always the same sorted list).
    // So the median of group s is always the same regardless of merge order within s. Good.

    let mut dp = vec![i64::MAX; full];

    // Base cases: single lists
    for i in 0..n {
      dp[1 << i] = 0;
    }

    for mask in 1..full {
      if mask.count_ones() < 2 { continue; }
      // Enumerate all non-empty proper subsets
      let mut sub = (mask - 1) & mask;
      while sub > 0 {
        let comp = mask ^ sub;
        if sub < comp {
          // Only consider sub < comp to avoid double counting
          if dp[sub] < i64::MAX && dp[comp] < i64::MAX {
            let cost = dp[sub] + dp[comp]
              + subset_len[mask] as i64
              + (median[sub] - median[comp]).abs();
            if cost < dp[mask] {
              dp[mask] = cost;
            }
          }
        }
        sub = (sub - 1) & mask;
      }
    }

    dp[full - 1]
  }
}