Лимит времени 1000/1000/1000/1000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Problem description
Brothers Tom and John went shopping. They bought N items each with a weight of wi. Now they want to pack them into two bags one for each of them and go home. Help them to divide items into two groups so that their weights are as close to each other as possible.
Input
There is a single integer N on the first line of input (1 ≤ N ≤ 250) and N integers wi on the second line ( 1 ≤ wi ≤ 250).
Output
On the first line write the weights of the first group and the second group.
On the second line write which items belong to the first group.
On the third line write which items belong to the second group.
Example
| stdin |
stdout |
|
7
23 65 134 32 95 123 34
|
252 254
1 3 5
2 4 6 7
|
Для отправки решений необходимо выполнить вход.
|