Caminho

Em um reticulado de N linhas e N colunas, cada célula contém um valor inteiro positivo. Queremos encontrar o caminho ortogonal mais leve possível entre a célula inicial (superior esquerda) e a célula final (inferior direita). Vamos definir leveza da seguinte maneira. Dado um caminho ortogonal c, seja max(c) o maior valor que ocorre em c; e seja len(c) o número de células em c. Dados dois caminhos ortogonais a e b, dizemos que a é mais leve do que b se:

• max(a) < max(b); ou
• max(a) = max(b) e len(a) < len(b).

No exemplo acima, q é mais leve do que p, pois max(q)=4 e max(p)=9; e r é mais leve do que q, pois max(r)=max(q)=4, mas len(r)=11 e len(q)=17.

Entrada

A primeira linha da entrada contém um inteiro N representando a dimensão do reticulado. Cada uma das N linhas seguintes contém N inteiros positivos V definindo os valores nas células do reticulado.

Saída

Seu programa deve produzir uma única linha, contendo dois inteiros, separados por um espaço em branco: max(c) e len(c) de um caminho ortogonal c mais leve possível no reticulado.

Restrições

• 2 ≤ N ≤ 300 e 1 ≤ V ≤ 10⁹

Informações sobre a pontuação

• Em um conjunto de casos de teste cuja soma é 20 pontos: N ≤ 100 e V ≤ 100

• Em um conjunto de casos de teste cuja soma é 40 pontos: N ≤ 100

Exemplos

5
2 1 4 3 3
9 7 9 9 2
2 3 1 4 1
1 9 4 3 7
1 4 2 2 1

4 11

5
1 7 1 1 1
7 9 9 9 1
7 7 8 1 1
9 7 8 1 9
9 7 7 1 1

7 9

2
1 1
1 100

100 3