Similar to the official editorial, but we can implement it simpler by bitwise operation, i.e., each bit should denote it’s possible to pay x yen if the x’th bit is 1, impossible otherwise.

(Ref) Japanese post for application of bitwise operation

AC code