Это сложная версия задачи. Единственное различие состоит в том, что в этой версии \(1 \le n \le 300\).
В кинотеатре места могут быть представлены как таблица из \(n\) рядов и \(m\) столбцов. Ряды нумеруются целыми числами от \(1\) до \(n\). Места в каждом ряду нумеруются последовательными целыми числами слева направо: в \(k\)-м ряду от \(m (k - 1) + 1\) до \(m k\) для всех рядов \(1 \le k \le n\).
| \(1\) | \(2\) | \(\cdots\) | \(m - 1\) | \(m\) |
| \(m + 1\) | \(m + 2\) | \(\cdots\) | \(2 m - 1\) | \(2 m\) |
| \(2m + 1\) | \(2m + 2\) | \(\cdots\) | \(3 m - 1\) | \(3 m\) |
| \(\vdots\) | \(\vdots\) | \(\ddots\) | \(\vdots\) | \(\vdots\) |
| \(m (n - 1) + 1\) | \(m (n - 1) + 2\) | \(\cdots\) | \(n m - 1\) | \(n m\) |
Таблица с номерами мест Есть \(nm\) людей, которые хотят прийти в кинотеатр, чтобы посмотреть новый фильм. Они пронумерованы целыми числами от \(1\) до \(nm\). Вы должны задать ровно одно место для каждого человека.
Известно, что в этом кинотеатре чем меньше номер места, тем лучше виден экран. У \(i\)-го человека уровень зрения \(a_i\). Обозначим за \(s_i\) номер места \(i\)-го человека. Необходимо выдать место лучше тем, у кого зрение хуже, то есть для любых двух людей \(i\), \(j\) таких, что \(a_i < a_j\), должно выполняться условие \(s_i < s_j\).
После того, как вы определите места всем людям, они начнут их занимать. В порядке от \(1\) до \(nm\) каждый человек входит в зал и садится на своё место. Чтобы сесть, человек подходит к своему ряду и начинает двигаться от первого места в ряду к своему слева направо. Во время того, как человек будет занимать свое место, какие-то места будут свободны, какие-то будут заняты теми людьми, которые уже вошли в зал. Неудобство человека равно количеству занятых мест, мимо которых он прошёл, пока занимал своё место.
Рассмотрим пример: \(m = 5\), человеку определено место \(4\) в первом ряду, причём места \(1\), \(3\), \(5\) в первом ряду уже заняты, а места \(2\) и \(4\) свободны. Неудобство этого человека будет равно \(2\), потому что он пройдет мимо двух занятых мест: \(1\) и \(3\).
Найдите минимальное общее неудобство (сумму неудобств всех людей), которое можно получить, задав места для всех людей (при этом все условия должны быть выполнены).
Примечание
В первом наборе входных данных существует единственный способ рассадить людей: первого человека посадить на первое место, а второго — на второе. Тогда суммарное неудобство будет равно \(1\).
Во втором наборе входных данных оптимальная рассадка выглядит следующим образом:
В третьем наборе входных данных оптимальная рассадка выглядит следующим образом:
Число в клетке обозначает индекс человека, занимающего это место.