SPOJ Brasil

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

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 ⊆ {g₁,g₂,...,g_N} dos N guerreiros disponíveis em Westeros para lutar por si. Cada guerreiro g_i (1 ≤ i ≤ N) tem dois inteiros associados a ele: sua força natural F_i e seu fator motivacional M_i. Se um dado subconjunto S de guerreiros é escolhido, então um guerreiro g_i ∈ S entrará no campo de batalha com uma força igual a F_i + |{g_j ∈ S : F_j > F_i}|*M_i. 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 g_i ∈ 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 ⊆ {g₁, g₂, ..., g_N} 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 ≤ 10³) indicando o número de guerreiros disponíveis. A segunda linha contém N inteiros distintos F_i (0 ≤ F_i ≤ 10⁶) separados por espaço, indicando a força natural dos guerreiros g₁, g₂, ..., g_N. Por fim, a terceira linha contem outros N inteiros M_i (-10³ ≤ M_i ≤ 10³, M_i ≠ 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