Cho một ma trận A kích thước $N \times M$, hãy đếm xem có bao nhiêu ma trận con (nhỏ nhất $1 \times 1$, lớn nhất $N \times M$) thỏa mãn tổng tất cả các số trong ma trận con không vượt quá số nguyên K cho trước?

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên N, M và K. Sau đó là N dòng, mỗi dòng chứa M số nguyên, biểu diễn ma trận A.

Dữ liệu ra

Một số nguyên là đáp án.

Ví dụ

Input

3 4 10
1 2 3 4
5 6 7 8
9 10 11 12

Output

19

Ghi chú

Giải thích ví dụ

Có tổng cộng 19 ma trận con thỏa mãn điều kiện, bao gồm: Kích thước 1×1 có 10 ma trận. Kích thước 1×2 có 3 ma trận. Kích thước 1×3 có 2 ma trận. Kích thước 1×4 có 1 ma trận. Kích thước 2×1 có 3 ma trận.

Quy mô test và ràng buộc

Với 30% dữ liệu, $N,M≤20$. Với 70% dữ liệu, $N,M≤100$. Với 100% dữ liệu, $1 \le N,M \le 500$, $0 \le A_{ij} \le 1000$, $1 \le K \le 250000000$.