Of the Children

BFS state explosion. state is city we're at and amount of money we have. Optimize for lowest "debt" incurred. Solution is the minimum debt that gets you to the final city with any amount of money. That debt is the amount you have to start with to ensure you have enough.