## Twin Towers

We all are aware of the famous twin towers, the demolition of which is one of the darkest days in the history and which forced world to take terror very seriously. Now after these many years many countries are trying to replicate the famous twin towers. But the problem is security these towers will always be a matter of concern.

India is also trying to replicate the twin towers. And the Indian engineers have come up with an idea to minimize the loss in case of any terror attack. They are planning to complete it block wise, such that each block is separable from the tower (although it is easier saying than done). So they are concentrating on preparing the blocks.

Once the blocks are completed, these blocks will be put upon each other to form the towers. The Government has asked them to keep the height of both the towers same and it should be as tall as possible. Once the blocks are completed they can’t go back. They have to build the towers using those blocks only and with these constraints.

Suppose the team has completed the blocks and are now looking for someone’s help to find out such an arrangement. Can you help them? You need not use all the blocks.

Input will be the number of blocks, n (0<51). The next line contains the height of each block. The height will of each block will be less than 500001

Output

Output will be the largest possible height of the towers. Print -1 in case no towers can be made.

Sample Input

2

11 11

3

2 3 5

3

9 1 11

Sample Output

11

5

-1

using System;

using System.Collections.Generic;

using System.Text;

using System.Text.RegularExpressions;

using System.Collections;

namespace ConsoleApplication1

{

class Program

{

static void Main(string[] args)

{

string blocks = "7 2 1 4 5 4";

Regex reg = new Regex(" ");

ArrayList arrayBlock = new ArrayList();

foreach (string val in reg.Split(blocks))

{

}

Console.WriteLine("Number of Blocks = " + arrayBlock.Count);

arrayBlock.Sort();

int sum = 0;

int numberOfBlocks = 0;

for (int iter = 0; iter < arrayBlock.Count; iter++)

{

if (iter != 0)

{

arrayBlock = AntiClockRotate(arrayBlock);

}

int sum1 = 0, sum2 = 0;

for (int i = arrayBlock.Count – 1; i >= 0; i–)

{

if (sum1 > sum2)

{

sum2 = sum2 + (int)arrayBlock[i];

}

else

{

sum1 = sum1 + (int)arrayBlock[i];

}

if (sum1 != 0 && sum2 != 0 && sum1 == sum2)

{

if (sum < sum1)

{

sum = sum1;

numberOfBlocks = arrayBlock.Count – i;

}

}

}

}

Console.WriteLine("Maximum Height of the Twin Tower = " + sum);

Console.WriteLine("Number of Blocks Used = " + numberOfBlocks);

}

public static ArrayList AntiClockRotate(ArrayList arr)

{

int temp = (int)arr[0];

for (int i = 0; i < arr.Count – 1; i++)

{

arr[i] = arr[i + 1];

}

arr[arr.Count – 1] = temp;

return (arr);

}

}

}

Output
=====================================
Number of Blocks = 6
Maximum Height of the Twin Tower = 11
Number of Blocks Used = 5
Press any key to continue . . .