Quebra-cabeças
Um quebra-cabeças é composto por um tabuleiro composto por células quadradas organizadas em duas linhas de N colunas. Cada célula do tabuleiro pode conter uma ficha numerada, como na figura abaixo.
As fichas podem ser deslizadas para uma célula não ocupada à direita ou à esquerda da posição corrente da ficha, mas a ordem das fichas, da esquerda para a direita, não pode ser alterada. Assim, na figura acima as fichas -3 e 5 podem ser movidas no máximo uma célula para a direita ou para a esquerda; já a ficha 3 pode ser movida somente para a esquerda, uma ou duas células. A figura abaixo ilustra algumas configurações possíveis para o quebra-cabeça da figura acima.
O valor de uma configuração é a soma das multiplicações entre as fichas da primeira e da segunda linha do tabuleiro, para cada coluna (a ausência de ficha em uma célula é equivalente à presença de uma ficha de valor zero). Ou seja, para a configuração (a) acima, o valor é 2 × -1 + -3 × 0 + 5 × 2 + 0 × 3 = 8; para a configuração (b), o valor é 2 × -1 + -3 × 0 + 0 × 2 + 5 × 3 = 13; para a configuração (c), o valor é 0 × -1 + 0 × 2 + 2 × 3 + -3 × 0 + 5 × 0 = 6. O objetivo do quebra-cabeça é encontrar uma configuração com o maior valor possível.
Dada a descrição do tabuleiro e das fichas do quebra-cabeças, escreva um programa para determinar o maior valor possível que uma configuração pode ter.
Entrada
A primeira linha da entrada contém um inteiro N, o número de colunas do tabuleiro. Cada uma das duas linhas seguintes descreve as fichas de uma linha do tabuleiro. A linha da entrada inicia com um inteiro M indicando o número de fichas na linha do tabuleiro, seguido de M inteiros Xi indicando o valor e ordem das fichas.
Saída
Seu programa deve produzir uma única linha, contendo um único número inteiro, o valor máximo de uma configuração para o quebra-cabeças da entrada.Restrições
- 1 ≤ N ≤ 500
- 1 ≤ M ≤ N
- -100 ≤ Xi ≤ 100 e Xi ≠ 0 para 1 ≤ i ≤ M
Informações sobre a pontuação
- Para um conjunto de casos de testes valendo 20 pontos, 1 ≤ N ≤ 10 e M = N-1.
- Para um conjunto adicional de casos de testes valendo 30 pontos, 1 ≤ N ≤ 200.
- Para um conjunto adicional de casos de testes valendo 50 pontos, nenhuma restrição adicional.
Exemplos
Entrada
5 3 2 -3 5 3 -1 2 3 |
Saída
19 |
Entrada
6 4 -20 7 13 -2 5 1 -2 7 1 -1 |
Saída
133 |
