I solved it using pretty straigtforward DP O(n * m^2), obviously it's just a complexity without any additional factors but it doesn't seem to be fitting time limit. Somehow it did. But I wonder, is there any more intricate idea for a faster solution?

Pay attention to: "wants to see the name of their company in the exactly s_i DIFFERENT problem statements"