Є \(N\) працівників, пронумерованих числами від 1 до \(N\), і \(N\) робіт, також пронумерованих числами від 1 до \(N\). Якщо i-й працівник виконує j-ту роботу, то йому виплачується заробітна плата у розмірі \(Cij\) грошових одиниць.

Необхідно знайти таке призначення працівників на роботи (кожен працівник виконує рівно одну роботу, кожна робота виконується рівно одним працівником), щоб сумарна зарплата працівників мінімальна (відповідна сума називається вартістю призначення).

Напишіть програму, яка розвязує задачу про призначення.

Формат вхідних даних

Перший рядок містить ціле число \(N\) (\(1 \le N \le 300\)).

Наступні \(N\) рядків містять по \(N\) чисел кожен. При цьому j-те число (i + 1)-го рядка дорівнює \(Cij\) (\(0 \le ≤ Cij \le 20000\)).

Формат вихідних даних

Виведіть мінімальну можливу вартість призначення.

Приклад вхідних даних

2
1 2
2 4

Приклад вихідних даних

4