Pilha de Dados
Zezinho tem um conjunto de dados e gosta muito de brincar de fazer pilhas de dados. Cada dado de Zezinho é um cubo perfeito; cada uma das seis faces de um dado tem um número inteiro, entre um e seis. Os dados não são dados normais, ou seja, a soma dos números em faces oposta não é necessariamente sete, mas cada número entre um e seis aparece em exatamente uma face de cada dado. Zezinho montou uma pilha de dados e quer girar os dados, sem mudar a ordem deles, de forma que:
• para dois dados adjacentes na pilha, as faces que se tocam tem o mesmo número;
• a soma dos números de uma das faces da pilha deve ter o maior valor possível.
Tarefa
Sua tarefa é escrever um programa que, dada a descrição da pilha de dados, calcula o valor máximo da soma dos números em uma das faces da pilha.
Entrada
A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha da entrada contém um número inteiro N, indicando o número de dados na pilha (1 ≤ N ≤ 104). Cada uma das N linhas seguintes descreve um dado. A i-ésima linha contém seis números inteiros entre 1 e 6, separados por um espaço em branco, indicando os números nas faces do i-ésimo dado. Os números são dados na ordem A, B, C, D, E e F, correspondendo às faces indicadas na figura abaixo.
Saída
Seu programa deve imprimir, na saída padrão, uma única linha contendo o maior valor possível que pode ser obtido na soma dos números de uma das faces da pilha girando-se os seus dados.
Exemplo
Entrada: 2 1 2 3 4 5 6 1 2 3 4 5 6 Saída: 12
Entrada: 5 2 3 1 6 5 4 3 1 2 4 6 5 5 6 4 1 3 2 1 3 6 2 4 5 4 1 6 5 2 3 Saída: 29