carpet

题号：NC16638
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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).