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 ≤ 109
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
Entrada
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 |
Saída
4 11 |
Entrada
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 |
Saída
7 9 |
Entrada
2 1 1 1 100 |
Saída
100 3 |