송금

$N$명의 친구가 여행을 갔다. 여행 중에는 택시, 호텔 팁, 식당 식사처럼 여러 활동에 돈을 내야 하는 경우가 자주 생겼다. 여행이 끝난 뒤 친구들은 누가 누구에게 얼마를 빚졌는지 계산했고, 그 결과가 행렬 $A_{i,j}$이다. $A_{i,j}$는 친구 $i$가 친구 $j$에게 전체적으로 갚아야 할 바이탈라르 금액이다. 친구에게는 1번부터 번호가 붙어 있다. 모든 $i, j$에 대해 $A_{i,j} = -A_{j,i}$임이 보장된다.

이제 정산할 시간이다. 친구들은 모든 빚을 갚아 각자 잔액을 0으로 만들려고 한다. 채무자가 채권자에게 직접 송금하는 것이 가장 간단하다. 그러나 은행은 송금할 때마다 수수료를 떼어 간다. 그래서 친구들은 더 똑똑하게 정산하기로 했다. 각자 중요하게 여기는 것은 받을 돈과 낼 돈의 합계가 맞는지뿐이다. 누가 누구에게 보내는지는 상관없고, 마지막에 모든 계좌의 잔액만 맞으면 된다.

필요한 송금 횟수의 최솟값은 얼마인가?

첫 줄에 친구 수를 나타내는 자연수 $N$ ($1 \le N \le 16$)이 주어진다. 이어서 $N$개의 줄에 각각 정수 $A_{i,j}$가 $N$개씩 주어진다 ($-10^9 \le A_{i,j} \le 10^9$).

첫 번째(유일한) 줄에 모든 빚을 정산하는 데 필요한 송금 횟수의 최솟값을 정수로 출력한다.