Exercício de Basquete
Finalmente, uma quadra de basquete foi inaugurada. Com isso, Demid decidiu realizar uma sessão de exercícios de basquete. $$2n$$ estudantes vieram para a sessão de exercícios do Demid, e ele os alinhou em duas fileiras de mesmo tamanho (há exatamente $$n$$ pessoas em cada fileira). Os alunos são numerados de $$1$$ a $$n$$ em cada fileira, da esquerda para a direita.
Agora Demid quer escolher um time para jogar basquete. Ele escolherá os jogadores da esquerda para a direita, e o índice de cada jogador escolhido (sem contar com o primeiro tirado) será estritamente maior que o índice do jogador escolhido anteriormente. Para evitar dar preferência a uma das fileiras, Demid escolhe os alunos de tal forma que nenhum aluno escolhido consecutivamente pertença à mesma fileira. O primeiro aluno pode ser escolhido entre todos os $$2n$$ estudantes (não há restrições adicionais), e uma equipe pode ser composta por qualquer número de alunos.
Demid acha que, de modo a compor uma equipe perfeita, ele deve escolher os alunos de uma maneira em que a soma das alturas de todos os alunos escolhidos seja a maior possível. Ajude Demid a encontrar a altura máxima possível dos jogadores em uma equipe que ele possa escolher.
Entrada
A primeira linha da entrada contém um único inteiro $$n$$ – o número de estudantes em cada fileira.
A segunda linha da entrada contém $$n$$ inteiros $$h_{1,1}, h_{1,2}, …, h_{1,n}$$, onde $$h_{1,i}$$ é a altura do i-ésimo estudante da primeira fileira.
A terceira linha da entrada contém $$n$$ inteiros $$h_{2,1}, h_{2,2}, …, h_{2,n}$$, onde $$h_{2,i}$$ é a altura do i-ésimo estudante da segunda fileira.
Saída
Imprima apenas um inteiro, a altura total máxima possível dos jogadores em um time que o Demid pode escolher.
Restrições
- $$1 \leq n \leq 10^5$$
- $$1 \leq h_{1,i} \leq 10^9$$
- $$1 \leq h_{2,i} \leq 10^9$$
Exemplos
Entrada |
Saída |
| 5 9 3 5 7 3 5 8 1 4 5 | 29 |
| 3 1 2 9 10 1 1 | 19 |
| 1 7 4 | 7 |
No primeiro exemplo, Demid pode escolher a seguinte equipe:
No segundo exemplo, Demid pode escolher a seguinte equipe:
