I know it’s usually bad form to post working code here, but this one is kind of an exception. And a warning to boot.
Source (if you’ve got access): https://www.codingame.com/training/community/hit-the-road/solution?id=5579986
Underlying message: problem authors, please… don’t make your problems so easily bruteforceable!