### Problem Statement

The usual longhand scheme for multiplying two numbers A and B is to multiply the last digit of B by A, shift left by one digit, multiply the second-to-last digit of B by A, and so on. This process is illustrated below:

```   36
x  15
-----
180
+ 36
-----
540
```

But let's say we didn't multiply in the usual way. Let us define a new method of multiplication called "NC-Multiplication", where the "NC" stands for "No Carry". It is called this because we do not carry when numbers exceed 9, no matter what. To multiply 36 by 15 in this manner, we would do:

```     3  6
x    1  5
---------
15 30
+ 3  6
---------
3 21 30
```

and so the result would be {3, 21, 30}.

You will be given a int[] digits, that represents the result of NC-multiplying two numbers together. You wish to factor this result by finding the two numbers that multiplied together to form the result. There may be multiple pairs of numbers that work. If we call the larger number A and the smaller B, then we want the pair such that A - B is minimized. Of this pair, your method should return a long that is equal to A. If no such A and B exist that NC-multiply to digits, your method should return -1.

### Definition

 Class: NCMultiplication Method: findFactors Parameters: int[] Returns: long Method signature: long findFactors(int[] digits) (be sure your method is public)

### Constraints

-digits will contain between 1 and 15 elements, inclusive.
-All elements of digits will be between 0 and 2000, inclusive.
-At least one element in digits will be nonzero.
-The number represented by digits will be less than 1014 = 100000000000000.
-There will be no leading or trailing zeros in digits.

### Examples

0)

 `{3,21,30}`
`Returns: 36`
 36 and 15 NC-Multiply together to make {3,21,30}, as seen above.
1)

 `{15,3,6}`
`Returns: 512`
2)

 `{4,20,25}`
`Returns: 25`
 25 NC-Multiplied by 25.
3)

 `{6,61,124,129,90,27}`
`Returns: 6773`
4)

 `{8,14,22,95,125,120,73,9,9}`
`Returns: -1`
5)

 `{6, 5, 32, 68, 113, 143, 143, 124, 100, 75, 48, 23, 7, 1}`
`Returns: 65864431`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5075&pm=2416

antimatter

#### Testers:

lbackstrom , brett1479