開心國的歡樂市正在進行都市更新，其中的愉快路旁的人行道有一項重鋪地磚的工程。愉快路附近的住戶希望鋪設好的人行道能夠展現地方特色，所以委託都市規畫的設計團隊進行人行道的設計。設計團隊在這條人行道預留了一列共 $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(\mathtt{\text{count}}(S,c_i)\times w_i)$$

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

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

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