Problem
Handsome Jack quer montar suas próprias fábricas de processamento de Eridium.
Existem n fábricas sob o controle de Jack, cada uma delas é numerada de 1 a n. Cada usina está localizada no depósito de Eridium, onde também é extraída em combinação. E quanto maior o número de fábrica, mais novo ele é.
Cada usina tem seu índice de eficiência a
i. Pode ser positivo, negativo ou zero.
Cada planta deve processar minério de Eridium. Você pode usar sua própria jazida ou levar minério, processado no passado por outra usina, por meio do mineroduto. No entanto, este processo é um pouco limitado. Em primeiro lugar, para não sobrecarregar o sistema de dutos, cada usina pode aceitar minério para processamento posterior estritamente uma da outra (ou não aceitar e usar seu próprio depósito). Em segundo lugar, as usinas mais antigas não são tecnicamente capazes de reprocessar o minério após uma usina mais nova.
O desempenho final de todo o sistema é calculado da seguinte forma: para cada planta, sua eficiência a
i é tomada e multiplicada pela etapa de processamento, que é calculada como o número de vezes que o minério de entrada é processado (para mais detalhes, veja as explicações dos exemplos), então todos os valores obtidos são resumidos para todas as plantas.
Ajude Handsome Jack a organizar o sistema para que o desempenho geral de todo o sistema seja o mais alto possível.
Entrada:
A primeira linha contém um número natural n (1 <= n <= 7) - o número de fábricas.
A segunda linha contém n inteiros separados por espaços, onde o i-ésimo número é a
i (-1000 <= a
i <= 1000) - a eficiência básica da planta sob o número i.
Saída:
Imprima um único número - o desempenho total máximo possível de todo o sistema.
Exemplos:
| Entrada |
Saída |
3
1 5 3
| 20 |
3
1 5 -3 |
8 |
Explicações:
No primeiro exemplo, é mais lucrativo para a primeira usina minerar seu próprio minério, a segunda usina receber minério da primeira e a terceira receber da segunda. Nesse caso, a primeira usina realiza processamento primário e sua produtividade é 1 * 1 = 1. A segunda usina realiza processamento secundário, sua produtividade é 5 * 2 = 10. E a terceira usina processa o minério recebido pela terceira vez, então sua produtividade é 3 * 3 = 9. O desempenho total é 1 + 10 + 9 = 20.
Observe que, neste exemplo, a segunda e a terceira plantas não podem ser trocadas, porque a segunda usina não poderá processar minério após a terceira por questões técnicas, por ser mais antiga que a terceira.
No segundo exemplo, a primeira e a terceira fábricas utilizarão suas jazidas, e a segunda fábrica receberá o minério da primeira.