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$

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.