# 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 ${\displaystyle x_{i}}$ equals ${\displaystyle 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 ${\displaystyle x_{i}}$ equals ${\displaystyle y_{i}}$. If you choose to break ${\displaystyle x_{i}}$ first the total cost will be '2 + 2*2', and the same will go for if you decide to break ${\displaystyle y_{i}}$ first. So the final conclusion is that cost of vertical breaking is: ${\displaystyle result=result+x_{i}*horizontalBreaks}$

And the same goes for horizontal breaks: ${\displaystyle result=result+y_{i}*verticalBreaks}$

```1

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

```42
```