### Problem Statement

You are given a sequence of digits. You must insert either a '+' (addition) operator or a '*' (multiplication) operator between each pair of adjacent digits in such a way that minimizes the value of the resulting expression. The expression should be evaluated using the standard order of operations (multiplication has a higher precedence than addition).

You will be given a String sequence. Perform the procedure described above on the sequence and return the resulting expression. If there are several possible answers, return the one that comes first lexicographically. Note that '*' comes before '+' lexicographically.

### Definition

 Class: OperationsArrangement Method: arrange Parameters: String Returns: String Method signature: String arrange(String sequence) (be sure your method is public)

### Constraints

-sequence will contain between 2 and 50 characters, inclusive.
-Each character in sequence will be a digit ('0'-'9').

### Examples

0)

 `"222"`
`Returns: "2*2+2"`
 The minimal result can be obtained in three ways: "2*2+2", "2+2*2" and "2+2+2". The first one comes first lexicographically.
1)

 `"322"`
`Returns: "3+2*2"`
2)

 `"307"`
`Returns: "3*0*7"`
3)

 `"391118571"`
`Returns: "3+9*1*1*1+8+5+7*1"`
4)

 `"111221911212"`
`Returns: "1*1*1*2*2*1+9*1*1+2*1*2"`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=5952

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8082&pm=5952

Andrew_Lazarev

#### Testers:

PabloGilberto , brett1479 , Olexiy

#### Problem categories:

Brute Force, Dynamic Programming, Math