Brincadeira de Criança

Nativos da pequena ilha de Tookutoo adoram matemática, e ensinam a suas crianças vários jogos e passatempos que envolvem problemas matemáticos. Um passatempo popular em Tookutoo é jogado com fichas de cerâmica como as ilustradas na figura abaixo.

Como pode ser visto, as fichas são similares a peças de dominó, sendo divididas em duas partes; em cada uma das partes está gravado um valor inteiro. As fichas acima têm valores [2, 1], [6, 3] e [3, 1]. Note que uma ficha [a, b] pode ser também escrita [b, a].

O passatempo inicia com o jogador recebendo um conjunto de fichas escolhidas aleatóriamente de um reservatório de fichas grande e variado. Usando o conjunto dado, o jogador deve dispor as fichas lado a lado, de tal forma que a soma dos valores das partes superiores das fichas seja igual à soma de valores das partes inferiores. Por exemplo, para o conjunto de fichas da figura acima, um arranjo correto possível é

1 6 1
2 3 3

Se não é possível encontrar uma disposição adequada com as fichas recebidas, o jogador pode descartar uma das fichas, mas o valor da soma da disposição deve ser a maior possível.

Tarefa

Você deve escrever um programa que, dado um conjunto de fichas, imprime a soma de uma disposição que satisfaz as condições do passatempo.

Entrada

A entrada é composta de vários conjuntos de testes. A primeira linha de um conjunto de teste contém um inteiro N indicando o número de fichas (0 ≤ N ≤ 400). Cada uma das N linhas seguintes contém dois inteiros Xi e Yi que descrevem uma ficha (0 ≤ Xi ≤ 1000) e (0 ≤ Yi ≤ 1000). O valor de N = 0 indica o final da entrada.

Exemplo de Entrada

4
1 4
2 9
2 1
0 4
2
8 1
9 4
3
6 3
1 2
3 1
0

Saída

Para cada conjunto de teste da entrada seu programa deve produzir três linhas. A primeira linha identifica o conjunto de teste, no formato "Teste n", onde n é numerado a partir de 1. A segunda linha descreve o resultado, na forma descrita a seguir. Se não é possível encontrar uma disposição adeqüada, imprima a palavra "impossivel" (note a ausência de acentuação). Se é possível encontrar uma disposição adeqüada, imprima a soma e a descrição da ficha descartada (se houver). Se é necessário descartar uma ficha, imprima "descarte X Y" onde X < Y; caso contrário imprima "descarte nenhum". A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Exemplo de Saída

Teste 1
10 descarte 1 2

Teste 2
impossivel

Teste 3
8 descarte nenhuma

Restrições

0 ≤ N ≤ 400 (N igual a zero apenas para indicar o final da entrada))
0 ≤ Xi ≤ 1000
0 ≤ Yi ≤ 1000