#include <iostream> #include <cstring> #include <cstdio> using namespace std; int dp[2000][30]; string s; int cost[27][27]; int ntest; int f(int x, int y){ int & res = dp[x][y]; if(res!=-1) return res; if(x == s.length()) return res=0; res = 10000000; for(int i=y; i<26; i++ ){ int temp = cost[s[x]-'a'][i] + f(x+1,i); res = min(res,temp); } return res; } void solve(){ cin>> s ; //cout << s << endl; for(int i=0; i<26; i++){ for(int j=0; j<26; j++){ cin >> cost[i][j]; } } memset(dp,-1,sizeof dp); int res = f(0,0); string r; int cur = 0; for(int i=0; i < s.length(); i++){ //cout << i << " "<< r << " "<< dp[i][cur] << " " << (char) ('a'+cur) << endl; for(int j=cur; j<26; j++){ if( dp[i][cur] == dp[i+1][j] + cost[s[i]-'a'][j] ){ cur = j; r += (char)('a'+j); cur = j; break; } } } cout << res << " " << r << endl; } int main(){ //freopen("test.in","r",stdin); cin >> ntest; while(ntest--){ solve(); } return 0; }