I've stumbled upon a version of this problem with smaller constraints on another site: 177 — G2 and managed to solve it using a naive approach (I believe it'd get me 30% of the points in this version aswell).

But I really want to know the intended solution that works with such large constraints, any help is appreciated, thanks