...hm. i think my inituition was way off

O(min(m^(1/2), n^(2/3))*m)

... is actually really good.