TopCoder

User's AC Ratio

55.6% (10/18)

Submission's AC Ratio

59.4% (63/106)

Description

開心國的歡樂市正在進行都市更新,其中的愉快路旁的人行道有一項重鋪地磚的工程。愉快路附近的住戶希望鋪設好的人行道能夠展現地方特色,所以委託都市規畫的設計團隊進行人行道的設計。設計團隊在這條人行道預留了一列共 $n$ 塊地磚的空格,打算鋪設一些顏色獨特的地磚。獨特的地磚顏色有紅色、綠色以及藍色,三種顏色的地磚分別以 r, g, b 表示。設計團隊將這 $n$ 個空格由左而右依序編號為 $1$ 至 $n$,每一種可能的地磚鋪法可用一長度為 $n$ 的字串 $S$ 表示,字串的第 $i$ 個字元 $S[i]$ 代表第 $i$ 個空格要鋪設的地磚顏色。

為了顧及群眾的喜好,歡樂市長蒐集了愉快路附近居民的意見,並彙整成一份「美觀意見」清單,清單裡共有 $k$ 項美觀意見。其中第 $i$ 項美觀意見由一個「美觀顏色組合」$c_i$ 和「美觀加權」$w_i$ 組成,$c_i$ 是一個由 rgb 三種字元所組成的字串,$w_i$ 是一個正整數。

我們可以根據這個清單為每一種地磚鋪法評定一個「美觀總分」$t$,定義為

$$
t = \sum_{i=1}^ k
(\texttt{count}(S, c_i) \times w_i)
$$

其中 $\texttt{count}(x, y)$ 代表字串 $y$ 在字串 $x$ 中出現的次數,例如 $\texttt{count}(\texttt{aaabaa}, \texttt{aa}) = 3$,因為由 aaaba 中的第 1、2、5 個字元分別作為字串開頭,都能找出子字串 aa;故 aaaaaba 中共出現三次。由 上式可得知總分 $t$ 會等於所有「美觀顏色組合 $c_i$ 在鋪法字串 $S$ 中出現的次數乘上該項美觀加權」的總和。

此外,某些地磚的顏色已經被附近的住戶指定,這些地磚的顏色將不能被改變。顏色指定的狀況同樣能以一長度為 $n$ 的字串 $T$ 表示;若第 $i$ 個空格的地磚顏色尚未被指定,則 $T[i] = \texttt{x}$;若第 $i$ 個空格的地磚顏色已經被指定,則 $T[i]$ 將會是 rgb 三個字元其中之一,代表此格地磚被指定的顏色。

請你寫一個程式來協助設計團隊鋪設地磚,使得美觀總分最大。

Input Format

輸入共 $k + 2$ 行。第一行為兩個正整數 $n$ 與 $k$,以一個空白分隔,分別表示待鋪設的地磚數以及美觀意見有幾項。

接下來有 $k$ 行,其中第 $i$ 行 ($1 \leq i \leq k$) 有一字串 $c_i$ 及一正整數 $w_i$,兩者間以一個空白分隔,分別代表第 $i$ 個美觀意見的「美觀顏色組合」及「美觀加權」。

最後一行有一個長度為 $n$ 的字串 $T$,由 rgbx 四種字元組成,表示目前街上地磚的指定狀況。

Output Format

輸出一個整數,代表不違反住戶要求的前提下,最大可能的「美觀總分」。

Sample Input

Sample Input 1
7 1
rgbr 1
rxbxgxx

Sample Input 2
18 4
rr 6
gg 5
b 1
rbg 2
xxgxxxxxxxxxxxxgxx

Sample Output

Sample Output 1
2

Sample Output 2
86

Hints

• $1 \leq n \leq 10000$,且 $n$ 為整數。
• $1 \leq k \leq 100$,且 $k$ 為整數。
• 任意美觀顏色組合字串 $c_i$,滿足 $c_i$ 長度在 $1$ 到 $2000$ 之間 (包含 $1$ 與 $2000$),且 $c_i$ 僅由 rgb 三種字元組成。
• 所有美觀顏色組合字串 $c_i$ 的長度加總小於等於 $2000$。
• 對所有 $1 \leq i \leq n$,滿足 $w_i$ 為整數,且 $1 \leq w_i \leq 200$。
• 對所有 $1 \leq i < j \leq k$,滿足 $c_i \neq c_j$。
• $T$ 的長度恰為 $n$,且 $T$ 僅由 rgbx 四種字元組成。

本題共有五組測試題組,條件限制如下所示。每一組可有一或多筆測試資料,該組所有測試資料皆需答對才會獲得該組分數。
1. ($16\%$) $n \leq 8$。
2. ($21\%$) 住戶的要求字串中沒有 x 字元。
3. ($45\%$) $c_i$ 長度至多為 $7$。
4. ($18\%$) 無額外限制。

Problem Source

2020 TOI 入營考
testdata set by Omelet

Subtasks

No. Testdata Range Constraints Score
1 0~9 $n \leq 8$ 16
2 10~19 住戶的要求字串中沒有 x 字元 21
3 20~29 $c_i$ 長度至多為 $7$ 45
4 0~39 無額外限制 18

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 4
1 1000 524288 65536 1 4
2 1000 524288 65536 1 4
3 1000 524288 65536 1 4
4 1000 524288 65536 1 4
5 1000 524288 65536 1 4
6 1000 524288 65536 1 4
7 1000 524288 65536 1 4
8 1000 524288 65536 1 4
9 1000 524288 65536 1 4
10 1000 524288 65536 2 4
11 1000 524288 65536 2 4
12 1000 524288 65536 2 4
13 1000 524288 65536 2 4
14 1000 524288 65536 2 4
15 1000 524288 65536 2 4
16 1000 524288 65536 2 4
17 1000 524288 65536 2 4
18 1000 524288 65536 2 4
19 1000 524288 65536 2 4
20 1000 524288 65536 3 4
21 1000 524288 65536 3 4
22 1000 524288 65536 3 4
23 1000 524288 65536 3 4
24 1000 524288 65536 3 4
25 1000 524288 65536 3 4
26 1000 524288 65536 3 4
27 1000 524288 65536 3 4
28 1000 524288 65536 3 4
29 1000 524288 65536 3 4
30 1000 524288 65536 4
31 1000 524288 65536 4
32 1000 524288 65536 4
33 1000 524288 65536 4
34 1000 524288 65536 4
35 1000 524288 65536 4
36 1000 524288 65536 4
37 1000 524288 65536 4
38 1000 524288 65536 4
39 1000 524288 65536 4