Общежитие ОшГУ
В новом общежитии Ошского государственного университета n свободных мест, и ровно n первокурсников ждут заселения. Студенты приехали из разных уголков страны — из Баткена, Нарына, Таласа, Каракола, — а места находятся в разных корпусах и на разных этажах.
Комендант Гульнара эже провела опрос и для каждого студента i и каждого места j оценила неудобство c[i][j]: сколько минут в день студент будет тратить на дорогу до своего факультета, с поправкой на этаж, соседей и пожелания. Некоторые сочетания недопустимы (например, места в женском блоке для юношей); они отмечены числом -1.
Нужно поселить всех студентов, каждого на отдельное место, так, чтобы суммарное неудобство было минимальным. Выведите это минимальное суммарное неудобство или -1, если поселить всех по правилам невозможно.
Входные данные
В первой строке — целое число n (1 ≤ n ≤ 500).
В каждой из следующих n строк — по n целых чисел: j-е число i-й строки равно c[i][j] (0 ≤ c[i][j] ≤ 10⁶ или c[i][j] = −1).
Выходные данные
Выведите одно целое число — минимальное суммарное неудобство или -1.
Пример 1
Вход:
3
4 1 3
2 0 5
3 2 -1
Выход:
6
Пример 2
Вход:
2
5 -1
7 -1
Выход:
-1
Пояснение
В первом примере выгодно поселить первого студента на место 3, второго — на место 2, третьего — на место 1: 3 + 0 + 3 = 6. Во втором примере оба студента могут жить только на месте 1.
Система оценивания
| Подзадача | Баллы | Дополнительные ограничения |
|---|---|---|
| 1 | 15 | n ≤ 12 |
| 2 | 25 | n ≤ 100 |
| 3 | 60 | без дополнительных ограничений |
Баллы за подзадачу начисляются, только если пройдены все её тесты.
Комментарии