Balancing the Matrix

Given a matrix of dimensions (M $\times$ N), you are allowed to perform the following operation: select any element from the matrix and either increase or decrease it by (1). You must perform exactly (K) such operations. The objective is to make the elements within each row as similar as possible. Additionally, you need to minimize the value represented by the following expression:

Input

The first line of the input contains two integers, (M) and (N) ((1 $\le$ M, N $\le$ 1000)). The next (M) lines each contain (N) integers, which define the matrix (A). Each of these integers is within the range of (-10^9) to (10^9). The final line contains an integer (K) ((0 $\le$ K $\le$ 10^18)).

Output

On the first line of the output, print the minimum value (d) that can be achieved after performing (K) operations. In the subsequent (M) lines, print the resulting matrix.

Examples