# Buy And Sell Stocks - K Transactions Allowed

easy

1. You are given a number n, representing the number of days. 2. You are given n numbers, where ith number represents price of stock on ith day. 3. You are given a number k, representing the number of transactions allowed. 3. You are required to print the maximum profit you can make if you are allowed k transactions at-most. Note - There can be no overlapping transaction. One transaction needs to be closed (a buy followed by a sell) before opening another transaction (another buy).

## Constraints

0 <= n <= 20 0 <= n1, n2, .. <= 10 0 <= k <= n / 2

## Format

### Input

A number n .. n more elements A number k

### Output

A number representing the maximum profit you can make if you are allowed a single transaction.

## Example

Sample Input

6
9
6
7
6
3
8
1

### Sample Output

5

Question Video