XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: quebra.x, onde x deve ser c, cpp, java, js ou py

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
	

 

Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação