Jelly, 39 38 37 bytes
ØhiⱮɠ’ḅ¥ȷ9Ṃ?⁴‘
Ỵṫ€⁵ḣ€40Fḟ⁶s2ṭ€⁾\xḣ¢ṫ¢
Now beats 05AB1E! (despite the lack of "convert from hexadecimal" builtin)
Same input format as Dennis' solution.
Use Ɱ
, which is a new feature (short for Ѐ
). Without it, this would take 3938 bytes.