Một nhà đầu tư trong lĩnh vực tiền số đang nằm giữ một danh sách dự đoán giá của một loại tiền số trong ~n~ ngày tới (từ ngày ~1~ đến ngày ~n~), ngày thứ ~i~ có giá trị là ~a_i~. Nhà đầu tư này muốn tối ưu hóa lợi nhuận của mình thông qua việc mua và bán loại tiền số này. Tuy nhiên, việc mua bán phải tuân theo các quy tắc sau:

1. Giới hạn giao dịch: Nhà đầu tư chỉ được phép thực hiện tối đa $k$ lần giao dịch. Mỗi giao dịch bao gồm một lần mua và một lần bán.

2. Số lượng tiền số nắm giữ: Tại bất kỳ thời điểm nào, nhà đầu tư chỉ có thể giữ tối đa một đồng tiền số. Điều này có nghĩa là phải bán đồng tiền hiện tại trước khi có thể mua một đồng tiên khác.

3. Không sở hữu ban đầu: Ban đầu, nhà đầu tư không sở hữu bất kỳ đồng tiền số nào.

Yêu cầu: Hãy lập trình xác định lợi nhuận lớn nhất nhà đầu tư này có thể thu được.

Subtask:

~- 20\%~ số điểm tương ứng với các test có ~n \leq 10^3, k = 1~.

~- 20\%~ số điểm tương ứng với các test có ~n \leq 10^5, k = 1~.

~- 20\%~ số điểm tương ứng với các test có ~n \leq 10^5, k = 2~.

~- 20\%~ số điểm tương ứng với các test có ~n \leq 10^3, k = n~.

~- 20\%~ số điểm tương ứng với các test có ~n \leq 10^5, k \leq 10^3~.

Ví dụ 1:

Input:

5 1
5 1 2 3 4

Output:

3

Ví dụ 2:

Input:

4 4
1 2 3 4

Output:

3