그림 교환

누가 누구에게 얼마에 팔 수 있는지 주어질 때, 1번을 시작으로 각 되팔기 가격이 산 가격보다 낮아지지 않게 하면서 서로 다른 사람이 가장 많이 소유하는 연쇄를 찾는다.

보통6동적 계획법비트 연산그리디그래프면접 대비아직 제출이 없습니다시간 제한2초메모리 제한128 MB

문제 설명

예제5

문제

예술을 사랑하는 사람들이 시장에 모여 한 그림을 거래하려고 한다. 모든 거래는 다음 두 조건을 만족해야 한다.

그림을 팔 때는 자신이 산 가격보다 크거나 같은 가격으로 팔아야 한다.
같은 사람이 같은 그림을 두 번 이상 살 수 없다.

시장에 새 그림 하나가 들어왔다. 1번 예술가는 이 그림을 외부 상인에게 가격 0으로 샀고, 이제 다른 예술가들에게 팔 수 있다. 위 조건을 만족하는 거래만 이루어진다고 할 때, 한 번이라도 그림을 소유한 사람 수의 최댓값을 구하시오. 1번 예술가와 마지막 소유자도 수에 포함한다.

입력

첫째 줄에 예술가의 수 N이 주어진다. N은 2 <= N <= 15를 만족하는 정수이다.

둘째 줄부터 N개의 줄에는 각각 N개의 숫자가 주어진다. i번째 줄의 j번째 숫자는 j번 예술가가 i번 예술가에게서 그 그림을 살 때 지불하는 가격이다. 가격 0이 가장 낮고, 가격 9가 가장 높다.

출력

잠시라도 그림을 소유했던 사람을 모두 포함하여, 그림을 소유할 수 있는 사람 수의 최댓값을 출력한다.