Description

Give you a expression,you can add some parenthesis to maximize result.Example as following:
1 + 2 * 3
Its result is 7 in the example.But you can add a parenthesis like (1 + 2) * 3,then the result is 9,and so it is the maximization of the example.You job is to find the maximizaton of a expression. To simplify this problem,you can assume that expression contains only operator + and *,but note that integers may be negative.

Input

Input contains multiple test cases.Each case begin with a integer N(2<=N<=100), the number of integers of a expression.Then follows the expression.Integers and operator spearate with a single whitespace.

Output

For each case print a single line with the maximized value of the expression.

Sample Input

4
1 + 2 * 3 + -1

Sample Output

8

void Test
{
    int i = Maximize("1 + 2 * 3 + -1"); //i=8
}

class Node
{
    public int Value {get; set;}
    public char Operator {get; set;}
    public static Node operator &(Node n1, Node n2)
    {
        int result = 0;
        switch(n1.Operator)
        {
            case '+': result = n1.Value + n2.Value; break;
            case '*': result = n1.Value * n2.Value; break;
        }
        return new Node() { Value = result, Operator = n2.Operator };
    }
}

int Maximize(string expression)
{
    List<Node> nodes = new List<Node>();
    int lastValue = 0;
    foreach (string s in expression.Split(' '))
    {
        if ("+-/*".Contains(s))
        {
            nodes.Add(new Node() { Value = lastValue, Operator = s[0]});
        }
        else
        {
            lastValue = int.Parse(s, System.Globalization.CultureInfo.InvariantCulture);
        }
    }
    nodes.Add(new Node() { Value = lastValue, Operator = '+' });

    Node[,] matrix = new Node[nodes.Count, nodes.Count];
    for (int e = 0; e < matrix.GetLength(0); e++)
    {
        matrix[e, e] = nodes[e];
        for (int s = e - 1; s >= 0; s--)
        {
            Node max = new Node(){Value = int.MinValue};
            for (int split = e - 1; split >= s; split--)
            {
                Node node = matrix[s, split] & matrix[split + 1, e];
                if (node.Value > max.Value) max = node;
            }
            matrix[s, e] = max;
        }
    }
    return matrix[0, matrix.GetLength(0)-1].Value;
}

------解决方案--------------------