Збалансування матриці

Задано матрицю розміром M×N. Вам дозволено виконувати наступну операцію: вибрати будь-який елемент матриці та або збільшити його, або зменшити на 1. Необхідно виконати рівно K таких операцій. Потрібно досягти, щоб елементи в кожному рядку відрізнялися один від одного якомога менше. Крім того, слід мінімізувати величину

Вхідні дані

У першому рядку вхідного файлу задано два цілі числа M і N (1 ≤ M, N ≤ 1000). У наступних M рядках наведено по N чисел, що визначають матрицю A. Усі ці числа цілі та не перевищують 10^9 за абсолютною величиною. В останньому рядку задано ціле число K (0 ≤ K ≤ 10^18).

Вихідні дані

У першому рядку вихідного файлу виведіть мінімальне значення d, якого можна досягти після K операцій. У наступних M рядках виведіть отриману матрицю.

Приклади