I think for any event card you first pay the cost (or overpay, in this case) and the start resolving its ability (its text). In fact, in the rules (version 1.6) it says that:
"Each time a player plays an event card, that player places it faceup on the table in front of them (the event is not in play), pays its costs, resolves its effects (unless those effects are canceled), and then places the card in its owner’s discard pile after those effects resolve (or are canceled)."
So you first pay and then resolve. Shuffling the cards back in the deck is part of the effect of the card. Paying takes place strictly before.