Cross-Border FX Router

Problem Statement

Cross-Border FX Router Problem Description G-P runs global payroll using multi-currency wallets. You start with a base currency B (e.g., USD). You must fund a set of payouts in various currencies. You can convert between currencies using directed FX corridors. Each corridor has: a rate r (converting x units of source yields r * x units of destination), and a flat destination-currency fee f that is deducted per conversion on that corridor. You may chain conversions arbitrarily. Corridors have no capacity limits. For each payout (Ci, Pi), you must ensure at least Pi units of currency Ci are deliverable after all conversions and corridor fees. Determine the minimum total amount of base currency B you must start with to fulfill all payouts. If any payout currency is unreachable from B, output -1. Key Property For a corridor u -> v with (rate=r, fee=f), to arrive at y units in v (after fee), you must depart x units in u such that: r * x - f >= y => x >= (y + f) / r This makes the required s