Given a string $$$S (|S| \le 100)$$$ and $$$n (n \le 1000)$$$ strings $$$T_1, T_2, \dots, T_n (|T_i| \le 30)$$$. Each string $$$T_i$$$ has a corresponding point $$$p_i (1 \le p_i \le 10000)$$$.

You can do the following operation any number of times (until you cannot choose any substring): Choose a substring in $$$S$$$ that is equal to one of $$$T_i$$$, delete that substring in $$$S$$$, you get $$$p_i$$$ points and the remaining characters of $$$S$$$ concatenate.

What is the maximum points you can get by doing the operations?

I was thinking about a solution using DP and Aho Corasick.

Specifically, let $$$dp(i, j) = $$$ the maximum points you can get with the first $$$i$$$ characters of $$$S$$$ and you are standing at node $$$j$$$ in the Trie after doing some operations.

But I came across a problem. When we move from $$$dp(i, j)$$$ to $$$dp(i + 1, k)$$$, if we jump from node $$$j$$$ to node $$$k$$$ with suffix link, we lost some information of the prefix that we haven't used in any operation yet.

Could you guys suggest any alternatives?

Thanks in advance.