Cardano-cli cannot submit tx, budget overspent

I’m trying to unlock some token at a script address, so I create a tx with cardano-cli transaction build … this passes successfully, then I sign the tx. It is now ready for submit but when I submit I get this error:
Command failed: transaction submit Error: Error while submitting tx: ShelleyTxValidationError ShelleyBasedEraAlonzo (ApplyTxError [UtxowFailure (WrappedShelleyEraFailure (UtxoFailure (UtxosFailure (ValidationTagMismatch (IsValid True) (FailedUnexpectedly [PlutusFailure "\nThe 3 arg plutus script (PlutusScript ScriptHash \"9f8863d5eb3f855c406ff38f29daa84e41ba0f3f1203bbe54275cf5f\") fails.\nCekError An error has occurred: User error:\nThe budget was overspent. Final negative state: ({ cpu: -119092 | mem: -400 })

After this I get a detail of the Tx followed by a big patch of non-readable text. (This same error also appears in the output of the syncing testnet node I’m running) Anyone knows what’s the issue and how to solve it? Thanks