Maximum K Rises

Given an integer array nums and an integer k, select at most k index pairs

(i_1, j_1), (i_2, j_2), ..., (i_m, j_m) with m <= k

such that:

• each pair is ordered: i_p < j_p;
• the pairs do not overlap and appear in order: each pair ends before the next one begins, i.e. j_p < i_{p+1}.

The score of a pair (i, j) is nums[j] - nums[i]. Return the maximum possible total score.

You may select fewer than k pairs, including none at all, so the answer is never negative.

Examples

Example 1

Input: k = 2, nums = [2,4,1]
Output: 2
Explanation: Select the single pair (0, 1): nums[1] - nums[0] = 4 - 2 = 2. No combination of pairs scores higher.

Example 2

Input: k = 2, nums = [3,2,6,5,0,3]
Output: 7
Explanation: Select pairs (1, 2) and (4, 5): (6 - 2) + (3 - 0) = 4 + 3 = 7.