Олимпиадаға дайындық аясында мұғалімдерге мектеп ғимаратындағы екі оқу кабинетiн таңдау қажет. Ғимарат \(H \times W\) өлшемді тор түрінде көрсетілген.

Әр кабинет \((i, j)\) ұяшығында орналасқан. Онда жұмыс орнын жабдықтау үшін \(A_{i,j}\) бірлік ресурс қажет.

Сондай-ақ, бұл кабинеттер арасында жиі қозғалу керек болады. Сондықтан \((i, j)\) және \((i', j')\) кабинеттерінің арақашықтығына байланысты қосымша шығындар болады:

\(C \times (|i - i'| + |j - j'|)\)

мұндағы \(C\) — қозғалыс шығын коэффициенті.

Екі әртүрлі кабинетті таңдап, жалпы шығын (екі орын + қозғалыс) минималды болатындай етіп таңдаңыз.

Енгізу

Бірінші жолда үш бүтін сан берілген: \(H\), \(W\), және \(C\) (\(2 \le H, W \le 10^6\), \(H \cdot W \le 10^6\), \(0 \le C \le 10^9\)) — тор өлшемдері мен қозғалыс коэффициенті.

Келесі \(H\) жолда \(W\) бүтін саннан: \(A_{i,j}\) (\(1 \le A_{i,j} \le 10^9\)) — \((i,j)\) кабинетінде жұмыс орнын жабдықтау бағасы.

Шығару

Минималды толық шығынды шығарыңыз.

Бағалау жүйесі

Мысалдар

Енгізу 1

2 2 2
1 2
2 1

Жауап 1

5