String problem

Problem Description

This is a simple problem about string. Now a string S contains only ‘0’-‘9’. ?? wants to select a subsequence from this string. And makes this subsequence score maximum. The subsequence’s score is calculated as follows: Score= Value – Total_Cost The calculation of the Cost is as follows: If the number of characters x in the subsequence is kx, And the two coefficients are ax,bx,The cost of character x calculated as follows:

$$ \left\{\begin{matrix} cost[x]=0,kx=0\\ cost[x]=ax*(kx-1)+bx,kx\ne0 \end{matrix}\right.$$$$TotalCost=\sum_{i=0}^{9}cost[i]$$

The calculation of the Value is as follows: Value=0; for(int i=1;i<=length(substr);++i){ for(int j=1;j<=length(substr);++j){ if(i!=j) Value+=w[id[i]][id[j]]; } } id[i] is the position of the subsequence’s ith character in the original string,for example,if the original string is “13579”,and the subsubquence is “159”,then the array id ={1,3,5}. The w is a weight matrix.

Input

The first line contains an integer T, denoting the number of the test cases. For each test case, the first line contains one integers n, the length of a string. Next line contains the string S. Next ten lines,each line contains ai,bi,denote the char i’s(0-9) coefficients Next is a n*n matrix w. Limits: T<=20, 0<=n<=100 0<=ai<=bi<=1000 0<=w[i][j]<=50

Output

Each test output one line “Case #x: y” , where x is the case number ,staring from 1. y is the Maximum score.

Sample Input

1
3
135
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
0 0 3
1 0 0
4 0 0

Sample Output

Case #1: 3

Hint

we can choose “15”，id[]={1,3} then Value=w[1][3]+w[3][1]=7, Total_Cost=2+2=4，Score=7-4=3

Author

FZU

Source

2016 Multi-University Training Contest 4