Дано матриця \(𝑁 × 𝑁\) - \(a_{i,j}\)​.

Обчисліть перестановку \(𝑝_𝑖\), ​що зводять до мінімуму \(\sum_{𝑖= 0}^{𝑁− 1} 𝑎_{𝑖,𝑝_𝑖}\).

Виведіть мінімальну суму.

Обмеження

• \(1≤N≤500\)
• \(∣𝑎_{𝑖, 𝑗} ∣ ≤ 10^9\)

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

Наступні  \(N\) рядків містять цілі числа \(a_{i,j}\).

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

У вихідний потік виведіть відповідь.

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

3
4 3 5
3 5 9
4 1 4

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

9