# SPOJ CHOCOLA

## Summary

Compute the minimal cost of breaking the whole chocolate into single squares.

## Explanation

After careful observation you can see that you must always choose line with highest cost. Explanation for this is: Every time you choose to break a chocolate the cost of next breaks will increase, so it's pretty clear that we must first break the lines with highest cost.

The next observation is that, if $x_{i}$ equals $y_{i}$ , it doesn't matter which one you choose because the sum of these breaks will be the same. To see why this is true lets look at this example: Input:

```2 2
2
2
```

As you can see $x_{i}$ equals $y_{i}$ . If you choose to break $x_{i}$ first the total cost will be '2 + 2*2', and the same will go for if you decide to break $y_{i}$ first. So the final conclusion is that cost of vertical breaking is: $result=result+x_{i}*horizontalBreaks$ And the same goes for horizontal breaks: $result=result+y_{i}*verticalBreaks$ ```1

6 4
2
1
3
1
4
4
1
2
```

```42
```