首页 > 试题广场 >

carpet

[编程题]carpet

时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

White Cloud has a rectangle carpet of $n*m$ . $Grid (i,j)$ has a color $colorA[i][j]$ and a cost $costA[i][j]$ .
White Rabbit will choose a subrectangle $B$ of $p*q$ from $A$ and the color of each grid is $colorB[0...p-1][0...q-1]$ , the cost of $B$ is the (maximum number in the corresponding subrectangle of $costA*(p+1)*(q+1)$ ).
Then $colorB$ is continuously translated and copied in an infinite times, that is, expand $colorB$ into an infinite new matrix, $colorC$ , which satisfies $colorC[i][j]=colorB[i mod p][j mod q]$ .
White Rabbit must ensure that $colorA$ is a subrectangle of $colorC$ .
You need to find the minimum cost way.

输入描述:

The first line of input contains two integers 
For the next line of  lines, each line contains  lowercase English characters, denoting .
For the next line of  lines, each line contains  integers in range [0,1000000000], denoting .

输出描述:

Print the minimum cost.

示例1

输入

2 5
acaca
acaca
3 9 2 8 7
4 5 7 3 1

输出

说明

choose subrectangle colorA[1...1][3...4]=ca, After copying unlimited copies
colorC=
cacacacaca ...
cacacacaca ...
cacacacaca ...
cacacacaca ...
cacacacaca ...
.........
colorA is a subrectangle of colorC
the cost is max(3,1)*(1+1)*(2+1).

算法知识视频讲解