http://wcipeg.com/problem/noi99p3

Could someone please help with this problem? Best I could come up with was a (n^2.5) *m dp solution which will obviously timeout.

Found this blog online, but couldn't understand the idea (search + pruning). https://www.byvoid.com/blog/noi-1999-solution

Thanks!