77. Weight on Suffix

Weight on Suffix

題目敘述

給定字串 $s = s_0s_1\cdots s_{n-1}$ ，每個後綴 $s_is_{i+1}\cdots s_{n-1}$ 都有權重 $w_i$。

試回答 $m$ 個詢問，第 $j$ 個詢問會給一個字串 $t_j$，可以的操作是找一個（可能為空的）字串 $u_j$ 使得 $t_j + u_j$ 形成一個 $s$ 的後綴，而且該後綴權重要最大。

請對於每一個詢問 $t_j$ 回答最大權重可以是多少，若無法形成任何後綴則輸出 $-1$

$$ 1 \leq n, m \leq 10^5 $$

$$ \sum_{j} |t_j| \leq 10^5 $$

輸入

每筆測資只有一個輸入 第一行有兩個數字 $n, m$ 第二行有一個全小寫字串 $s = s_0 s_1\cdots s_{n-1}$ 第三行有 $n$ 個數字代表權重 $w_0, w_1, \cdots, w_{n - 1}$ 接下來 $m$ 行，每行有一個字串 $t_j$ 代表第 $j$ 個詢問

輸出

輸出 $m$ 行，第 $j$ 行有一個數字代表第 $j$ 個詢問的答案

Sample Input

7 5
ababaab
0 1 2 3 4 5 6
a
ab
aba
abab
ababb

Sample Output

5
5
2
0
-1

Sample Input

7 4
ababaab
4 2 3 5 6 1 0
a
ab
aba
abab

Sample Output

6
4
4
4

Judge Setting

run-time limit: 1000 ms
memory limit: 268435456 byte
測資數量: 22