小D的棋盘

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

小D有一个神奇的棋盘,棋盘有n行,m列。这个棋盘为什么神奇呢?因为这个棋盘被施加了一个魔法,小D每念一次咒语,棋盘上的棋子就能分裂到相邻的上下左右四个格子上,分裂之后原来的会消失,如果他的某个方向上没有格子(比如第一行没有向上的格子),那么他就不会向上分裂。现在小D想知道他念了k次咒语之后棋盘上现在会有多少个棋子。注意:每个格子能够放无数个棋子,分裂后的棋子再念一次咒语棋子能继续分裂。

Input

输入n,m。(2<=n<=20,2<=m<=20)表示棋盘的行列。

接下来n行,每行m个数字aij(0<=aij<=1),每个数字代表这个格子初始的时候有几个棋子。

接下来一行输入k(1<=k<=10)。

Output

输出一个数字表示小D念了k次咒语之后棋盘上现在会有多少个棋子。这个数字保证在int的范围内。

Sample Input

3 3
0 0 0
0 1  0
0 0 0
2

Sample Output

12

Hint

在示例中,念了一次咒语后棋盘的情况是:

0 1 0

1 0 1

0 1 0

再念一次后棋盘的情况是:

2 0 2

0 4 0

2 0 2

最终棋盘有12个棋子。

Source

cat_of_orange