Let's say they both have jobs that pay $70,000 (not too crazy of an assumption I don't think).
Combined income is $140,000. After taxes (35%), take home pay is $91,000.
That is $7583 per month.
Subtract $4500 for debt leaves them $3083.

They live in Minnesota, so housing shouldn't be too pricey. Let's say $1500 for housing expenses. That leaves them about $1500 a month for food and other stuff. Plenty to live on in my opinion

Is that too hard to believe? If they really crunched, they could do it much faster.