### Problem Statement

Suppose I want to make a decision rationally. One approach is to come up with several categories and weight each category according to its importance. Then I assign scores in each category to the competing alternatives, and pick the alternative with the highest total weighted score. For example, suppose I am buying a new car and I need to decide between a sedan, a minivan, or a sport-utility vehicle (SUV). In consultation with my wife, I come up with four categories

• cost (weight 3)
• carrying capacity (weight 2)
• fuel efficiency (weight 1)
• fun (weight 1)
After studying each vehicle carefully, we give them the following scores:

```  Vehicle     Cost  Cap.  Eff.  Fun      Total Score
----------------------------------------------------------
sedan        6     3     5     4      6*3+3*2+5*1+4*1 = 33
minivan      5     5     3     2      5*3+5*2+3*1+2*1 = 30
SUV          4     6     2     6      4*3+6*2+2*1+6*1 = 32
```
Clearly we should purchase the sedan. Unfortunately, neither of us wants the sedan. I really want the minivan, and my wife really wants the SUV. And so begins the process of rationalization, in which we each try to tweak the numbers to make our choice come out on top. She quickly realizes that by tweaking one number, changing the weight of the fun category from 1 to 2, she can cause the SUV to win with a score of 38 (versus 37 for the sedan and 32 for the minivan). I have to work harder, but if I tweak two numbers, changing the cost score of the minivan from 5 to 6 and the efficiency score of the sedan from 5 to 4, then I can make the minivan win with a score of 33 (versus 32 for both the SUV and the sedan). Note that there are several other tweaks that each of us could have made that would have achieved our respective goals.

Given the inital weights and scores, as well as the zero-based index desired of the alternative that you want to win, determine the minimum number of tweaks needed to make your chosen alternative win. To win, your chosen alternative must end up with a score strictly higher than all the other alternatives--ties are not good enough. A single tweak involves changing the value of a particular weight or a particular score up or down by one. The same number cannot be tweaked more than once, and a tweak may not cause a weight or a score to exceed 9 or drop below 1. If no amount of tweaking can make your chosen alternative win, return -1.

weights will be given as a int[], and scores will be given as a String[]. Element J of weights is the weight for category J, and element I of scores contains the scores for alternative I. Within element I of scores, character J represents the score for alternative I in category J. In the example above, weights would be { 3, 2, 1, 1 } and scores would be { "6354", "5532", "4626" }, with desired=2 for the SUV and desired=1 for the minivan. (See Examples 0 and 1.)

### Definition

 Class: Rationalization Method: minTweaks Parameters: int[], String[], int Returns: int Method signature: int minTweaks(int[] weights, String[] scores, int desired) (be sure your method is public)

### Constraints

-weights contains between 2 and 10 elements, inclusive.
-Each element of weights is between 1 and 9, inclusive.
-scores contains between 2 and 10 elements, inclusive.
-Each element of scores contains exactly W characters, where W is the number of elements in weights.
-Each character in scores is a digit between '1' and '9', inclusive.
-desired is between 0 and S-1, inclusive, where S is the number of elements in scores.

### Examples

0)

 `{ 3, 2, 1, 1 }` ```{ "6354", "5532", "4626" }``` `2`
`Returns: 1`
 The example above, trying to make the SUV win.
1)

 `{ 3, 2, 1, 1 }` ```{ "6354", "5532", "4626" }``` `1`
`Returns: 2`
 The example above, trying to make the minivan win.
2)

 `{ 3, 2, 1 }` ```{ "555", "333" }``` `1`
`Returns: -1`
 Option 1 can never beat option 0. The best it can do is tie.
3)

 `{ 1, 2, 3, 3 }` ```{ "9234", "1334" }``` `1`
`Returns: 3`
 Unfortunately, we can't drop the weight of the first category to 0.
4)

 `{ 8, 2 }` ```{ "55", "92" }``` `0`
`Returns: 6`
5)

 `{ 2, 8, 7, 3, 6, 5, 2, 4, 7, 2 }` ```{ "9197287893", "9492555365", "3459972761", "4886112198", "5963616776", "6325897129", "3248793133", "7984474438", "4518544769", "1592681682" } ``` `5`
`Returns: 17`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5870&pm=2347

vorthys

#### Testers:

PabloGilberto , lbackstrom , brett1479

#### Problem categories:

Brute Force, Greedy