Problem Statement

You are given an array a[1..N] and an integer Q , select a subsequence i 1 < i 2 < ... < i m to maximize its sum. Constraint: the number of inversions in the chosen subsequence (pairs t < u where a[i t ] > a[i u ] ) is at most Q . Return -1 if no non-empty valid subsequence exists (note: any single element has 0 inversions, so a solution always exists). Find the maximum sum of a non-empty subsequence of a such that the number of inversions in the chosen subsequence is at most Q Or -1 . Input Format The first line contains a integer, n , denoting the size of the array. The second line contains a integer, q , denoting the maximum allowed inversions in the chosen subsequence. The next line contains n space-separated integers, where the i -th integer represents a[i] (0 ≤ i < n ). Constraints 1 ≤ n ≤ 10 5 0 ≤ q ≤ 10 5 -10 9 ≤ a[i] ≤ 10 9 Sample Test Cases Case 1 Input: 3 0 10 20 30 Output: 60 Explanation: Only non-decreasing subsequences have 0 inversi