#### Жишээ тэстүүд

##### Оролт
10 2
2
7
3
9
8
7
9
7
1
9

##### Гаралт
15

##### Оролт
10 5
2
7
3
9
8
7
9
7
1
9

##### Гаралт
21


## Тэмдэглэл

In the first example, the best trade overall is to buy at a price of 1 on day 9 and sell at a price of 9 on day 10 and the second best trade overall is to buy at a price of 2 on day 1 and sell at a price of 9 on day 4. Since these two trades do not overlap, both can be made and the profit is the sum of the profits of the two trades. Thus the trade strategy looks like this:

2    | 7    | 3    | 9    | 8    | 7    | 9    | 7    | 1    | 9buy  |      |      | sell |      |      |      |      | buy  | sell

The total profit is then (9 - 2) + (9 - 1) = 15.

In the second example, even though Manao is allowed up to 5 trades there are only 4 profitable trades available. Making a fifth trade would cost Manao money so he only makes the following 4:

2    | 7    | 3    | 9    | 8    | 7    | 9    | 7    | 1    | 9buy  | sell | buy  | sell |      | buy  | sell |      | buy  | sell

The total profit is then (7 - 2) + (9 - 3) + (9 - 7) + (9 - 1) = 21.