Masala #TNBRI5X2ZF

Xotira 256 MB Vaqt 2500 ms
14

Qayta raqamlash

Zarifda N ta qator va M ta ustundan iborat natural sonlardan tashkil topgan A matritsa bor, u bu matritsani eslab qolishi kerak. Zarif matritsaning \(A[i ][ j ]\) elementini eslab qolish uchun \(A[i ][ j ]\) energiya sar aydi. Zarifga aslida A matritsaning aynan o’zi emas, undagi har bir \(A[i ][ j ]\) elementning o’zini qatoridagi hamda o’zining ustunidagi prioriteti muhim, ya’ni, qayta raqamlashdan oldin o’zini qatorida yoki ustunida nechta elementdan kichik bo’lgan bo’lsa, qayta raqamlangandan keyin ham shuncha elementdan kichik bo’lishi kerak.
Zarif matritsani eslab qolishga sar aydigan energiyasini imkon qadar kamroq qilish uchun matritsani qayta raqamlab chiqmoqchi. Qayta raqamlangan matritsa elementlari ham natural sonlardan tashkil topgan bo‘lishi hamda matritsani eslab qolish uchun sarflanadigan umumiy energiya (matritsaning umumiy yig’indisi) imkon qadar kamroq bo’lishi kerak
Zarifga matritsani qayta raqamlashda yordam bering.


Kiruvchi ma'lumotlar:

Kirish oqimining birinchi qatorida ikkita butun son, N, M(1 ≤ NM ≤ 106 ) sonlari kiritiladi. Keyingi N ta satrning M ta ustunida A[i ][ j ] (1 ≤ A[i ][ j ] ≤ 109) matritsa elementlari kiritiladi.


Chiquvchi ma'lumotlar:

Chiqish faylida N ta qatorda va M ta ustunda qayta raqamlangan matritsani chiqaring.


Misollar
# input.txt output.txt
1
2 2
1 2
3 4
1 2
2 3
2
4 3
20 10 30
50 40 30
50 60 70
90 80 70
2 1 3
5 4 3
5 6 7
9 8 7