SPOJ Brasil

Você foi contratado como programador para um novo website de compras coletivas chamado Macaco Rural. Para se diferenciar dos seus vários concorrentes, esse site planeja oferecer ofertas para pares de produtos. Por exemplo, “compre uma bola de futebol e uma camisa oficial da seleção brasileira com 75% de desconto”.

O site quer planejar as ofertas do dia para os próximos n dias. Para tanto, há uma lista de 2n produtos, com seus respectivos preços (já com os descontos aplicados). Como ofertas muito caras vendem menos, seu chefe quer minimizar o preço da oferta mais cara. Cabe a você agrupar os 2n produtos em n pares de forma tal que o custo do par mais caro seja minimizado. O custo de um par é a soma dos custos dos produtos que o compõem.

Entrada

Há vários casos de teste.

Cada caso de teste começa com uma linha que contém um único inteiro N, o número de produtos que serão usados para criar as ofertas (1 ≤ N ≤ 2.000.000, e N é sempre um número par). Em seguida, há uma linha contendo N inteiros P₁, P₂, ..., P_N, que representam os preços dos N produtos que serão pareados em N/2 ofertas (0 ≤ P_i ≤ 1.000.000.000, para todo i).

A entrada termina com N = 0, que não deve ser processado.

Saída

Para cada caso de teste, imprima uma linha contendo um único inteiro, que é o maior preço de uma oferta, quando os N produtos são pareados de forma tal a minimizar esse maior preço.

Exemplos

Entrada:
4
1 19 26 17
8
3 9 6 18 14 1 7 8
0

Saída:
36
19

No primeiro caso de teste, há 3 possibilidades:

• (1, 19), (17, 26), com custos 1+19=20 e 17+26=43. O maior custo é 43.
• (1, 26), (17, 19), com custos 1+26=27 e 17+19=36. O maior custo é 36.
• (1, 17), (19, 26), com custos 1+17=18 e 19+26=45. O maior custo é 45.

Dessas três opções, a que minimiza o maior custo é a segunda, que leva a um custo máximo de 36.