Пригощання корів

Корови відзначили ще один успішний місяць рекордного виробництва молока, і кожна з них заслужила особливе частування. Вони вишикувалися у прямокутнику розміром $w$ на $h$, очікуючи на винагороду.

Кожна корова має унікальний показник продуктивності F_{rc} (1 \le F_{rc} \le 1000000), що відображає її загальний внесок у виробництво молока. Фермер Джон вирішив, що справедливо буде роздавати частування, починаючи з найпродуктивніших корів. Він планує пройти по прямокутнику рядок за рядком, зліва направо, роздаючи частування в такому порядку.

Фермер Джон попросив корів реорганізуватися так, щоб найпродуктивніші корови отримали частування першими. Корови можуть обмінюватися місцями лише цілими рядками або стовпцями. Джон попросив їх зробити все можливе, щоб найкраща корова опинилася у верхньому лівому куті (рядок $1$, стовпець $1$), наступна краща — у рядку $1$, стовпець $2$ (якщо можливо), і так далі. Хоча корови не можуть повністю відсортувати себе, вони можуть дотримуватися такої стратегії:

• визначити порядок винагороди Фермера Джона:

• знайти корову з найвищим рейтингом. Обмінювати рядки та стовпці, поки вона не опиниться в рядку $1$, стовпець $1$. Після цього її більше не рухати.

• Потім повторювати наступне правило, доки можливо переставити якомога більше корів:

Знайти наступну корову з найвищим рейтингом. Обмінювати рядки та стовпці (не переміщуючи корів з вищим рейтингом) так, щоб перемістити її в найкраще доступне місце (наприклад, рядок $1$, стовпець $2$, якщо воно доступне, або рядок $2$, стовпець $1$, якщо в першому рядку немає вільних місць).

Наприклад, розглянемо множину з $3$ на $4$ корів:

Корова з рейтингом $99$ має найвищий рейтинг, тому її потрібно розмістити в лівому верхньому куті. Для цього обміняємо місцями рядки $1$ і $2$, а потім стовпці $1$ і $2$ (або навпаки — результат буде той самий):

Корова з рейтингом $11$ повинна бути винагороджена наступною після корови з найвищим рейтингом. Вона зараз у клітинці ($3$, $4$) — в останній клітинці, яка буде винагороджена. На цьому етапі вже занадто пізно перемістити її на перший рядок або навіть у перший стовпець. Її потрібно перемістити в ($2$, $2$), обмінявши стовпці $2$ і $4$, а потім рядки $2$ і $3$:

Корова з рейтингом $10$ отримує винагороду відразу після корови з $11$. Корова $9$ вже винагороджена. Корова з $8$ отримує винагороду відразу після корови з $10$. Корова з $7$ отримує винагороду відразу після корови з $8$. Корова з $6$ вже винагороджена. Корову з $5$ найкраще перемістити в рядок $3$, стовпець $2$, але рядки $1$ і $2$ заморожені, як і всі стовпці. Таким чином, корови $1$, $4$ і $5$ не рухаються, і друга діаграма вище — "найкраще, що можуть зробити корови".

Реалізуйте цей алгоритм для інших прямокутних масивів корів.