You are given an array events, where each element is a list [startDay_i, endDay_i, value_i] describing an event that starts on day startDay_i, ends on day endDay_i, and provides a value of value_i if you attend it.

You may attend at most k events. Attending an event requires you to be available for every day from startDay_i through endDay_i inclusive, so you cannot attend two events whose date ranges overlap.

Return the maximum total value you can obtain by attending at most k non overlapping events.

Note: You are not required to attend exactly k events.

Constraints:

• $1 \leq$ k $\leq$ events.length

• $1 \leq$ k $\cdot$ events.length $\leq 10^6$

• $1 \leq$ startDay_i $\leq$ endDay_i $\leq 10^9$

• $1 \leq$ value_i $\leq 10^6$

Input: events = [[1,3,5],[4,6,6],[7,7,4],[2,5,10],[6,8,7]]-List[List[int]], k = 2-int
Output: 17-int
Explanation: Attend event [2,5,10] (value 10), then event [6,8,7] (value 7). These do not overlap because the second starts after day 5, and the total 10 + 7 = 17 is maximal with at most 2 events.

Input: events = [[5,10,8],[6,9,9],[7,8,7],[5,7,6]]-List[List[int]], k = 3-int
Output: 9-int
Explanation: All events overlap in time (they all occur within days 5–10), so you can attend at most one event, and the best single event is [6,9,9] with value 9.

Input: events = [[1,1,2],[2,2,100],[3,3,3],[4,4,90],[5,5,4]]-List[List[int]], k = 2-int
Output: 190-int
Explanation: Since each event lasts exactly one day, none overlap if you pick different days. Choosing the two highest values, [2,2,100] and [4,4,90], gives a total of 100 + 90 = 190.

Input: events = [[100000000,100000000,50],[1,99999999,60],[100000001,100000002,70],[99999998,100000000,65]]-List[List[int]], k = 2-int
Output: 135-int
Explanation: A best choice is [99999998,100000000,65] (ending on day 100000000) and [100000001,100000002,70] (starting on day 100000001), which do not overlap, for a total of 65 + 70 = 135.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.