The farmer Yasuhiro has recently bought a rectangular plot. Prior to sowing time, the day before a full moon, he traced a rectangular grid on his plot and separated his seeds in two categories: medicinal plants and fruit trees. The land quality is, of course, not uniform. Some cells of the grid are better than others depending on certain factors such as soil permeability, coarseness, irrigation type, and ground slope. To quantify all those variables, Yasuhiro has defined a productivity factor for each cell: a number between 0 and 100 indicating how much he would benefit from sowing in that particular cell. Specifically, a factor of 0 means he would not benefit at all from that cell, while a factor of 100 means he would benefit the most. Yasuhiro has also made a table with information about the plant species he is going to sow. This table describes the category of each species (medicinal plant or fruit tree), its cost per cell, and the minimum and maximum possible number of cells occupied by that species. The total benefit from sowing one particular species in any particular cell is equal to the productivity factor of that cell times the cost per cell of that species. Given the number of rows and columns in the grid, the productivity factor of each cell, and the table with the plant information, you must calculate the maximum possible benefit which can be obtained by sowing according to the following rules: • In each cell, at most one plant species can be sown. • For every species, the number of cells where it is sown must be between the minimum and the maximum specified in the table. • No two cells in the same row can contain the same species of medicinal plant. Likewise, no two cells in the same column can contain the same species of fruit tree. • The total benefit is the sum of the individual benefits from each sown cell. Input The input consists of several test cases. The specification of each test case follows: • First, there is a line with three integers R, C, and E, which specify, respectively, the number of rows in the grid, the number of columns in the grid, and the number of species in the table (1 ≤ R ≤ 4, 1 ≤ C ≤ 4 and 1 ≤ E ≤ 10). • Then follow R lines, each one of them with C blank-separated integers between 0 and 100. The jth number of line i is the productivity factor of the cell in row i and column j. • Finally, there are E lines, one for each species in the table, each comprising the following blank- separated data: – The character ‘M’ if it’s a medicinal plant or ‘F’ if it’s a fruit tree. – An integer d which indicates the current species’ cost per cell (1 ≤ d ≤ 104). – Two integers n and m which are, respectively, the minimum and maximum number of cells for the current species (0 ≤ n ≤ m ≤ 4). The end of the input is given by R = C = E = 0, which should not be processed as a test case.
2/2 Output For each test case, print a line with the maximum possible benefit which Yasuhiro can obtain from sowing the plot according to the rules. If it is not possible to sow the plot as specified, then print ‘0’. Sample Input 221 10 10 10 10 M 3000 0 4 332 10 50 90 50 90 10 90 10 50 M 1500 3 3 F 500 3 3 221 100 100 100 100 F 2000 3 4 231 100 100 100 100 100 100 M 2000 0 3 000 Sample Output 60000 480000 0 400000