Tdetective

There is a group of n people. The people are numbered 0 through n-1. Person number 0 is the principal witness. Exactly one of people 1 through n-1 is the killer. In addition to the n people there is a single detective who wants to find the killer.

Whenever the detective talks to a person, he can determine with absolute certainty whether the person is the killer or not. Thus, all he needs to do is to talk to all the people in some order and he will certainly find the killer. However, the time needed to find the killer depends on the order in which the detective talks to the suspects.

During the investigation the detective maintains a list of his suspicion levels: for each person between 0 and n-1, inclusive, the suspicion level of that person is an integer between 0 and 9, inclusive. (The larger the number, the more the detective currently suspects the person.) Initially, the suspicion levels of all n suspects are equal to 0. At the beginning of investigation, the detective will interview the principal witness (person 0) and he will use the information he receives to update his suspicion levels. (The way this works is explained in detail below.)

The investigation then proceeds in rounds. Each round of investigation looks as follows: First, the detective must choose whom to interview next. Then, the detective interviews the chosen person. If that person is the killer, the investigation is over. Otherwise, the detective will receive new information from the witness and he will use it to update his suspicion levels.

When choosing whom to interview next, the detective decides as follows:

• He must choose a person he did not interview yet.
• Among those, he must choose a person with the highest suspicion level.
• Among those, he may choose any person.

You are given a String[] s with n elements, each with n characters. Each of those characters is a digit between 0 and 9, inclusive. The string s[i] is the information received when the detective interviews person i and that person is not the killer. For each j, the digit s[i][j] is the level to which person i and person j dislike each other. (Note that the information in s is symmetric: s[i][j] always equals s[j][i].) The more person i dislikes person j, the more incriminating evidence against person j will be presented by person i to the detective. When the detective receives this information, he will update the suspicion level of person j from its current value to the maximum of its current value and the value s[i][j]. (For example, after interviewing person 0 the detective's current suspicion level of each person j is increased from 0 to s[0][j].)

For each k between 1 and n-1, we are now going to solve the following problem: Assume person k is the killer. What is the smallest number of rounds of interviewing (NOT counting the initial interview with person 0) the detective needs to interview in order to find the killer? Let's denote the answer to this question as ans[k]. In other words, ans[k] is the smallest value X such that there is a valid sequence of X people the detective could interview after person 0 (according to the above rules) that ends with person k.

Compute the value ans[k] for each valid k. Return the sum of k*ans[k] over all valid k. (For example, if n=4, return the value 1*ans[1] + 2*ans[2] + 3*ans[3].)