XP and EG both like eating apple. This day they bought a lot of apples. Then it was time for them to seperate these apples. They didn't want to get less apples than each other and cut the apples into pieces either. So they would get equal weight of apples. After they seperated the apples, the rest would be throw away. for example they bought 5 apples, their weight are 1 2 3 5 6 , XP will get apple of weight 1 2 and EG 3 , the rest of 5,6 will be throw away. The total weight they get is 3. But there is another better way. XP get the apples of weight 2 6 and EG 3 5 , the total weight the get is 8, and this is the best way. But they didn't know how to seperate the apples. So they ask you for help to get as many apples as possible.

The first contain a positive integer n indicate the number of apple(1<=n<=100). you can sure the total weight of the apple won't exceed 2000.
The second line contain n integers indicate the weight of each apple.

A integer m,indicate the maximal weight XP and EG can get.