cho.sh

Painting Exchange

Given who can sell to whom at what price, find the longest chain of distinct buyers starting from artist 1 where each resale price never drops below the purchase price.

Medium6Dynamic programmingBit manipulationGreedyGraphInterviewNo attempts yetTime limit2sMemory limit128 MB

Problem

Artists who love art have gathered at a market to trade a painting. Every trade must satisfy both rules below.

  1. When an artist sells the painting, the sale price must be greater than or equal to the price they paid for it.
  2. The same artist cannot buy the painting more than once.

A new painting has just arrived at the market. Artist 1 bought it from an outside merchant for price 0, and can now sell it to other artists. Assuming only trades that satisfy the rules are made, find the maximum number of people who can own the painting at least once. Count Artist 1 and the final owner as well.

Input

The first line contains the number of artists, N. N is an integer with 2 <= N <= 15.

Each of the next N lines contains N digits. The j-th digit on the i-th line is the price that artist j pays to buy the painting from artist i. Price 0 is the lowest price, and price 9 is the highest.

Output

Print the maximum number of people who can own the painting, including anyone who owns it only briefly.