CODE THANKS FESTIVAL 2015 オープンコンテスト

H - 穴あきケーキ


Time limit時間制限 : 4sec / Memory limitメモリ制限 : 256MB

問題文

クリスマスの時期が近づいてきました。あなたは友達のためにクリスマスケーキとして穴あきケーキを作ることになりました。

穴あきケーキを作るために用いるケーキ生地は RC 列の長方形状であり、i (1 ≦ i ≦ R)j (1 ≦ j ≦ C) 列の領域を領域 (i, j) と呼ぶことにします。領域 (i, j) を食べたとき、C_{i,j} キロカロリー得られます。また、領域 (1, 1) が左上隅、領域 (R, C) が右下隅です。

あなたはこのケーキ生地を以下の手順によって穴あきケーキに加工します。

  • まず、4 つの整数 a, b, c, d (1 ≦ a < b ≦ R, 1 ≦ c < d ≦ C, b - a ≧ 2, d - c ≧ 2) を定めます。ケーキ生地のうち、領域 (a, c) を左上、(b, d) を右下とした長方形の部分を切り出します。
  • 先の手順で切り出した部分について、端に存在しない領域 1 つ (領域 (e, f) (a+1 ≦ e ≦ b-1, c+1 ≦ f ≦ d-1) とする) を選んで削除し、残りを穴あきケーキとします。

また、穴あきケーキの摂取カロリーは、穴あきケーキを構成する領域に定められたカロリーの合計値となります。

健康志向の友達は穴あきケーキを食べることによって得られる摂取カロリーがちょうど K キロカロリーとなるようなケーキを希望しています。あなたは条件を満たす穴あきケーキとして考えられるものの総数、すなわち、上記の条件を満たす 6 つの整数 a, b, c, d, e, f の選び方が全部で何通りあるかを計算することにしました。


入力

入力は以下の形式で標準入力から与えられる。

R C K
s_1
s_2
:
s_R
  • 1 行目には、ケーキ生地の行数 R (3 ≦ R ≦ 350)、列数 C (3 ≦ C ≦ 350) および友達が希望している摂取カロリー量 K (0 ≦ K ≦ 999,999) が空白区切りで与えられる。
  • 2 行目から R 行には、ケーキ生地のカロリーに関する情報が与えられる。このうち i (1 ≦ i ≦ R) 行目では 長さ C の文字列 s_i が与えられる。s_i を構成する文字はいずれも 1 から 9 までの数字である。s_i の左から j (1 ≦ j ≦ C) 文字目の数字は、領域 (i, j) を穴あきケーキに含めることによって増加するカロリー量 C_{i,j} に等しい。

出力

穴あきケーキとして考えられる総数を 1 行に出力せよ。出力の末尾にも改行を入れること。


入力例1

4 5 14
54311
11211
17312
11119

出力例1

2

ケーキ生地は下表のようになっています。

5 4 3 1 1
1 1 2 1 1
1 7 3 1 2
1 1 1 1 9

例えば、a = 2, b = 4, c = 1, d = 4 として切り出した場合、以下の領域が切り出されます。

1 1 2 1
1 7 3 1
1 1 1 1

さらに、e = 3, f = 2 として穴を開けると、穴あきケーキは以下の形状となります (* は穴を開けた場所を表す)。

1 1 2 1
1 * 3 1
1 1 1 1

このとき、摂取カロリーは、1+1+2+1+1+3+1+1+1+1+1 = 14 となり、条件を満たします。

他にも a = 1, b = 3, c = 3, d = 5, e = 2, f = 4 のときに条件を満たします。


入力例2

6 7 8
1111116
1111111
1111115
1113111
1211111
1111141

出力例2

7

穴あきケーキを構成する領域のカロリーの配置が同じでも、切り出す場所、穴を開ける場所が異なれば異なるケーキとして数えます。


入力例3

3 3 9
211
121
112

出力例3

0

条件を満たす穴あきケーキが存在しない場合もあります。


入力例4

8 8 15
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111

出力例4

100

Submit提出する