For each person, compute the savings of sending them to A instead of B: . A negative savings means A is cheaper. A positive savings means B is cheaper. Sort by this difference. Send the first people (most benefit from A) to city A, and the rest to city B. Why this works: you are prioritizing people who benefit most from each city. Sorting by difference measures opportunity cost, not absolute cost.
This maximizes total savings by ensuring people who benefit most from each city go to that city.