You are given an $n \times m$ matrix. Please select $k$ submatrices from it such that the sum of the values of these $k$ submatrices is maximized. Note: The selected $k$ submatrices must not overlap.

Input

The first line contains $n, m, k$ ($1 \le n \le 100, 1 \le m \le 2, 1 \le k \le 10$). The next $n$ lines describe the values of each element in each row of the matrix (the absolute value of each element does not exceed $32767$).

Output

A single line containing the maximum sum of the values of the $k$ submatrices.

Examples

Input 1

3 2 2
1 -3
2 3
-2 3

Output 1

9