Garden Fencing

Byteman has a garden of size L × W meters, divided into L × W cells (each of size 1×1). Each cell (x,y) with 1 ≤ x ≤ L and 1 ≤ y ≤ W contains a non‐negative integer number of roses. Initially, Byteman planted N roses in his garden. Now, with summer arriving and the roses in full bloom, he finds that he cannot manage all his roses by himself.

He decides to hire two gardeners, each to take care of a rectangular region of his garden. The two rectangular areas must satisfy the following conditions:

• Both rectangles have sides parallel to the garden boundaries. A rectangle is defined by two pairs of integers (L1, W1) and (L2, W2) such that 1 ≤ L1 ≤ L2 ≤ L and 1 ≤ W1 ≤ W2 ≤ W. It covers all cells (x,y) with L1 ≤ x ≤ L2 and W1 ≤ y ≤ W2.
• Each rectangle must contain exactly K roses (i.e. the sum of roses in its cells is K).
• The two rectangles must not intersect or overlap, i.e. they should not share any common cell. (Note: even if they share a common border, their perimeters are computed separately.)

The fence around each rectangular region follows its perimeter. For a rectangle defined by (L1, W1) and (L2, W2), its perimeter is given by:

Your task is to choose two such rectangles that satisfy the above conditions while minimizing the sum of their perimeters. If it is not possible to find two valid non-overlapping rectangles, output -1.

inputFormat

The first line contains three integers L, W, and K — the dimensions of the garden and the number of roses that must be in each chosen rectangle.

Then follow L lines, each containing W non-negative integers. The j-th number on the i-th line represents the number of roses in cell (i, j).

outputFormat

Output a single integer: the minimum sum of the perimeters of the two non-overlapping rectangular regions each containing exactly K roses. If no such pair of rectangles exists, output -1.

sample

3 3 1
0 1 0
1 0 1
0 1 0

8