### Problem Statement

One type of compression is run length encoding. In this case, a character may be preceded by an integer N, which indicates that the character should be repeated N times. For example, the String "3ABBC10D" would be decompressed as "AAABBCDDDDDDDDDD". A character that is not preceded by an integer is repeated just once. We are going to enrich this slightly be allowing a sequence of characters to be preceded by an integer N, indicating that the sequence should be repeated N times. In this case, the sequence of characters should be surrounded by parentheses. Additionally, you may nest the compressed sequences. Thus, the compressed sequence "X2(2A3(BC))X" would be decompressed as "XAABCBCBCAABCBCBCX". You will be given a String of uppercase letters and are to compress it in such a way that the result has as few characters as possible. If there are multiple ways to do this, choose the one that comes first lexicographically (using standard ASCII ordering).

### Definition

 Class: RunLengthPlus Method: compress Parameters: String Returns: String Method signature: String compress(String s) (be sure your method is public)

### Constraints

-s will contain between 1 and 50 uppercase letters, inclusive.

### Examples

0)

 `"AAABBCDDDDDDDDDD"`
`Returns: "3A2BC10D"`
1)

 `"XAABCBCBCAABCBCBCX"`
`Returns: "X2(2A3(BC))X"`
2)

 `"ABCBACBABCBABCABACACBCBABACBCBBABACBACBCACBBAC"`
`Returns: "ABCBA2(CBAB)CABACACBCBABACBC2BA2(BAC)BCAC2BAC"`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6553&pm=3961

lars2520

#### Testers:

PabloGilberto , Yarin , vorthys

#### Problem categories:

Dynamic Programming, Encryption/Compression, String Manipulation