Editor's note: This editorial has been copied from Codeforces. The official editorial seems to be unrelated.

~D[t][g] =~ the minimum cost we can obtain if we take the first ~t~ test cases and put them in ~g~ groups.

~D[t][g] = \min(d[k][g-1] + \operatorname{group\_cost}(k+1, t))~, where ~k~ is the last test of the previous group and ~\operatorname{group\_cost}(x, y)~ is the total score the participants will obtain on tests ~x~-~y~ if we group them.

The complexity is ~\mathcal{O}(T^2 S)~ but it is too big for 100 points. Let's assume that we are at test ~t~. Let's keep for each of the ~N~ participants the most recent test he failed and denote it with ~last~. For contestant ~x~, ~last[x] = \max(k)~, ~k \le t~ and ~x~ failed test ~k~.

Using those ~N~ values, we will divide our tests into ~N+1~ groups. Group ~1~ consists of all test cases from the most recent ~last[x]~ until ~t~ (basically, no one fails any tests in this group). Group ~2~ consists of all test cases from the second most recent ~last~ until the most recent ~last~ (only one participant fails the groups), etc. Let's denote for each group ~x~: ~best[x] = k~, where ~k~ is the best option we can select for our dynamic programming with the restriction that ~k~ is a test from group ~x~. Formally: ~d[k][g-1] + \operatorname{group\_cost}(k+1, t)~ is minimal for all ~k~ from group ~x~. If we know for each group this best, we will have to check only ~\mathcal{O}(N)~ different possibilities (since there are only ~N~ groups) and take the best option.

Let's assume that we solved ~D[t][g]~, formed all the groups and computed each ~best[x]~. Let's see what happens when we go to test ~t+1~. Assume initially that all participants pass this test. One of the key observations is that the "~best~" values do not change (all options increase with the same value in the same group), so we just have to recheck all the ~N+1~ possibilities. Now let's assume that contestant ~x~ fails test ~t+1~. The main modification is that ~last[x]~ becomes ~t+1~, so the groups change their configuration:

1. The previous ~last[x]~ was dividing 2 groups which now have merged into one. To compute the new best of this new group it is enough to just compare the two old options and take the best one.
2. All the options from the previous ~last~ to the new one change their value in the recursion. Unfortunately, it is necessary to loop throw all of them again since they changed drastically. Fortunately, we can do that with brute force and the complexity will not change (because a passed test will be recomputed only once between 2 consecutive failed tests).

The final complexity is ~\mathcal{O}(T S N)~.