154. DAY 4 PH. 字串雜湊

字串雜湊

題目敘述

如果我們給每個字元 $c$ 一個整數 $v_c$，那麼我們就可以遞迴地定義一個字串雜湊函數 $f$：

1. $f(c) = v_c \pmod{71234}$ ，如果 $c$ 是一個字元
2. $f(sc) = f(s)\times len(s) + f(c) \pmod{71234}$ ，如果 $s$ 是一個非空字串且 $c$ 是一個字元

對於一個長度為 $L$ 的字串，我們把長度整除 $L$ 的前綴按照長度從小到大編號 $p_1, p_2, ..., p_k$ ，其中 $k$ 是這種前綴的個數，並把這種前綴稱為拆分前綴，因此 $p_1=s_1$ 、 $p_k=s_1 s_2 ... s_L$。

給你 $n$ 個字串，請從每個字串裡選各選出一個拆分前綴出來，使得選出來的拆分前綴的雜湊值總和最小，並且選出來的拆分前綴的編號必須滿足一些條件。

輸入說明

第一行包含兩個正整數 $n,\,m\,(n\le 100, m\le200)$

接下來有一行，包含 $26$ 個整數，對應到 $v_a, v_b, ..., v_z$ 的值。 $(0\le v_a,...,v_z \le 71233)$

接下來有 $n$ 行，每行包含一個字串 $s_i\,(1≤|s_i|≤1000)$，$s_i$ 由小寫英文字母組成 $\sum_1^n |s_i| \le 100,000$

接下來有 $m$ 行，每行包含兩個數字 $x, y (1\le x,y\le n)$ ，代表第 $x$ 個字串所選的拆分前綴編號不能超過第 $y$ 個字串所選的拆分前綴編號

輸出說明

輸出一個整數，代表所選出來的拆分前綴們雜湊值的總和最小是多少

範例輸入 1

2 0
71233 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
ab
bc

範例輸出 1

3

範例輸入 2

2 1
71233 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
ab
bc
1 2

範例輸出 2

6

範例輸入 3

2 0
71233 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a
bc

範例輸出 3

71235

提示

對於一個字串，它從第一個字元開始的子字串稱為它的前綴。

Judge Setting

run-time limit: 1000 ms
memory limit: 64000000 byte
測資數量: 0