簡単のため、\(S_i \neq S_j ( i \neq j)\) であるとします。
\(S_1,S_2, \ldots ,S_N\) について \(S_i\) が \(S_j\) の部分文字列であるときに頂点 \(i\) から頂点\(j\) に有向辺が張られている \(N\) 頂点のグラフ \(G\) を考えます。このとき、\(G\) はDAG (Directed Acyclic Graph：有向非巡回グラフ) です。
また、各頂点に対して \(A_1,A_2, \ldots , A_n\) の重みが割り振られているとします。

このとき、今回の問題は以下のように言い換えることができます。

各頂点に重みが割り振られた、\(N\) 頂点のDAGが与えられます。
\(N\) 頂点のうちいくつかの頂点を選びます。ただし、選んだ頂点間にパスが存在するような \(2\) 頂点は選べません。
このとき、選んだ頂点の重みの総和の最大値を求めてください。

まずは重みがない場合に、頂点数を最大化する問題を考えます。
\(G\) は頂点\(i\) → 頂点\(j\) , 頂点 \(j\) → 頂点 \(k\) の辺があるとき必ず、頂点 \(i\) → 頂点 \(k\) の辺があります。このようなDAGにおいては Dilworth の定理 を用いることができます。

Dilworth の定理
頂点\(i\) → 頂点\(j\) , 頂点 \(j\) → 頂点 \(k\) の辺があるとき必ず、頂点 \(i\) → 頂点 \(k\) の辺があるDAG \(G\) について、
\((Gの最小パス被覆の大きさ)=(Gの最大独立集合の大きさ)\)
が成り立つ。

重みがない場合の問題は \(G\) の最大独立集合の大きさを求める問題であり、最小パス被覆の大きさを求める問題と等しいことがわかりました。
(最小パス被覆の大きさとは \(G\) の頂点をパスに分解したときのパスの個数としてありえる最小値を指します。)

実は、DAG \(G\) においては最小パス被覆は二部グラフの最大マッチングへ帰着することができます。

よって、重みがない場合(または全て等しい場合)の問題を解くことができました。しかし、今回の問題では選んだ頂点の重みの総和の最大値を求める必要があります。
実はこの問題は重みがない場合の二部グラフの最大マッチングの各頂点についてそれぞれの重みの個数だけ頂点があると考えることで同じ問題に帰着することができます。
この問題では重みが大きいため、重みの個数だけ頂点を作ることはできませんが、各頂点に対して\(S\) → \(v\) と \(v'\) → \(T\) の辺の最大容量を \(A_v\) とし、\(i\) → \(j'\) の辺の最大容量を \(\infty\) としたとき、頂点が重みの個数だけ存在した場合と同様の答えを求めることができます。
つまり、 \(( \sum A_i - (S → T の最大流))\) が答えとなります。

実装の際は \(S_i=S_j\) を満たす \(i,j\) に対してどのように辺を張るか考慮する必要がありますが、\(S_i = S_j\) かつ \(i<j\) の時に \(i→j\) の間に辺を張るなどして \(G\) を必ずDAGにすることで本問題は解くことができます。他にも同一の文字列について、最大の \(A\) をもつ頂点のみを有効な頂点として扱うような方法もあります。

計算量については、\(S_i\) が \(S_j\) の部分文字列であるかをすべての \(i,j\) の組に対しての判定は \(O(N^{2}+(\sum |S_i|)^2)\) ででき、頂点数 \(O(N)\) で辺数 \(O(N^{2})\) の二部グラフの最大流は ACL などでは \(O(N^{4})\) で求められるため、全体で \(O(N^{4} + (\sum |S_i|)^{2})\) で求めることができます。

実装例(C++):

#include <bits/stdc++.h>
#include <atcoder/maxflow>
using namespace std;
using ll = long long;
static constexpr ll inf = 1e10;

bool is_substring(const string& s, const string& t) {
    const int n = s.size(), m = t.size();
    for (int i = 0; i + m <= n; ++i) {
        if (s.substr(i, m) == t) return true;
    }
    return false;
}

int main() {
    int n;
    cin >> n;
    vector<string> s(n);
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) cin >> s[i];
    for (int i = 0; i < n; ++i) cin >> a[i];
    atcoder::mf_graph<ll> g(2 * n + 2);
    int source = 2 * n, sink = 2 * n + 1;
    for (int i = 0; i < n; ++i) {
        g.add_edge(source, i, a[i]);
        g.add_edge(i + n, sink, a[i]);
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i != j) {
                if (s[i] == s[j]) {
                    if (i < j) {
                        g.add_edge(i, j + n, inf);
                    }
                } else if (is_substring(s[i], s[j])) {
                    g.add_edge(i, j + n, inf);
                }
            }
        }
    }
    const ll flow = g.flow(source, sink);
    const ll sum = accumulate(a.begin(), a.end(), 0LL);
    cout << sum - flow << endl;
}