It's also correct. The word 'dia' refers to third singular person, whatever their gender is. As for additional 'the very' between at and least, it's just for extra emphasis, won't change anything drastically.

Wouldn't "he chose it already" be "dia telah memilih itu"?