Before revision:  We give two algorithms, a deterministic algorithm with  work complexity O( m^2n^2) and a randomized algorithm with  work complexity O( m^2n^2).
After revision:  We give two algorithms, a deterministic algorithm with work complexity O( mn^2), and a randomized algorithm with work complexity O( m^2n^2).