Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

JULGAMEN - Julgamento por Combate

Tyrion Lannister está sendo acusado de um crime terrível e exigiu que seu julgamento seja realizado por combate.

tyrion

Tyrion vive em Westeros. De acordo com as leis de Westeros, em um julgamento por combate, ambos réu e acusador escolhem guerreiros para combaterem entre si. Se os guerreiros escolhidos pelo réu vencerem o combate, o réu é absolvido; entretanto, se os guerreiros escolhidos pelo acusador vencerem, então o réu é condenado.

Pela lei de Westeros (na verdade, pela lei deste problema), o réu Tyrion pode escolher qualquer subconjunto S{g1,g2,...,gN} dos N guerreiros disponíveis em Westeros para lutar por si. Cada guerreiro gi (1 ≤ i ≤ N) tem dois inteiros associados a ele: sua força natural Fi e seu fator motivacional Mi. Se um dado subconjunto S de guerreiros é escolhido, então um guerreiro gi ∈ S entrará no campo de batalha com uma força igual a Fi + |{gj S : Fj > Fi}|*Mi. Em outras palavras, sua força natural será acrescida de seu fator motivacional multiplicado pelo número de guerreiros com força natural maior que a sua no conjunto S, já que o guerreiro pode se motivar ao lutar ao lado de guerreiros melhores.

Assim, por exemplo, se um guerreiro gi S tem força natural 10 e fator motivacional 2, sua força no campo de batalha será igual a 14 se houver outros 2 guerreiros com força natural maior que 10 lutando a seu lado em S. Note que é possível que o fator motivacional de um guerreiro seja negativo, caso no qual o guerreiro se desmotiva ao lado de guerreiros maiores. Assim, se o mesmo guerreiro tiver fator motivacional -2, sua força em batalha será igual a 6. Note que é possível, inclusive, que um guerreiro entre em batalha com força negativa.

A força total de um conjunto de guerreiros S é dada pela soma das forças dos guerreiros de S em batalha. Tyrion pediu sua ajuda para determinar qual subconjunto S ⊆ {g1, g2, ..., gN} ele deve escolher de forma a maximizar sua força total, aumentando assim suas chances de vitória. Note que Tyrion pode, se desejar, não escolher nenhum guerreiro, caso no qual a força total dos guerreiros escolhidos é igual a 0 (neste caso, ele mesmo irá lutar).

Entrada

A entrada contém vários casos de teste. Cada caso de teste inicia com uma linha contendo um inteiro N (1 ≤ N ≤ 103) indicando o número de guerreiros disponíveis. A segunda linha contém N inteiros distintos Fi (0 ≤ Fi ≤ 106) separados por espaço, indicando a força natural dos guerreiros g1, g2, ..., gN. Por fim, a terceira linha contem outros N inteiros Mi (-103Mi ≤ 103, Mi ≠ 0) indicando o fator motivacional dos guerreiros.

A entrada termina com N = 0.

Saída

Para cada caso de teste, imprima uma única linha contendo a força total do subconjunto que deve ser escolhido por Tyrion.

Examplo

Entrada:
2
7 10
2 4
3
10 20 30
-10 -50 100
0 Saída: 19
30

Adicionado por:Ricardo Oliveira [UFPR]
Data:2014-06-07
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:8o Contest Noturno

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.