<p>You are given an array of <code>events</code> where <code>events[i] = [startDay<sub>i</sub>, endDay<sub>i</sub>, value<sub>i</sub>]</code>. The <code>i<sup>th</sup></code> event starts at <code>startDay<sub>i</sub></code><sub> </sub>and ends at <code>endDay<sub>i</sub></code>, and if you attend this event, you will receive a value of <code>value<sub>i</sub></code>. You are also given an integer <code>k</code> which represents the maximum number of events you can attend.</p>

<p>You can only attend one event at a time. If you choose to attend an event, you must attend the <strong>entire</strong> event. Note that the end day is <strong>inclusive</strong>: that is, you cannot attend two events where one of them starts and the other ends on the same day.</p>

<p>Return <em>the <strong>maximum sum</strong> of values that you can receive by attending events.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2021/01/10/screenshot-2021-01-11-at-60048-pm.png" style="width: 400px; height: 103px;" /></p>

<pre>
<strong>Input:</strong> events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
<strong>Output:</strong> 7
<strong>Explanation: </strong>Choose the green events, 0 and 1 (0-indexed) for a total value of 4 + 3 = 7.</pre>

<p><strong class="example">Example 2:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2021/01/10/screenshot-2021-01-11-at-60150-pm.png" style="width: 400px; height: 103px;" /></p>

<pre>
<strong>Input:</strong> events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
<strong>Output:</strong> 10
<strong>Explanation:</strong> Choose event 2 for a total value of 10.
Notice that you cannot attend any other event as they overlap, and that you do <strong>not</strong> have to attend k events.</pre>

<p><strong class="example">Example 3:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2021/01/10/screenshot-2021-01-11-at-60703-pm.png" style="width: 400px; height: 126px;" /></strong></p>

<pre>
<strong>Input:</strong> events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
<strong>Output:</strong> 9
<strong>Explanation:</strong> Although the events do not overlap, you can only attend 3 events. Pick the highest valued three.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= events.length</code></li>
	<li><code>1 &lt;= k * events.length &lt;= 10<sup>6</sup></code></li>
	<li><code>1 &lt;= startDay<sub>i</sub> &lt;= endDay<sub>i</sub> &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= value<sub>i</sub> &lt;= 10<sup>6</sup></code></li>
</ul>

class Solution:
    def search_next(self, cur: int) -> Optional[int]:
        if cur >= len(self.events):
            return None
        cur_end = self.events[cur][1]
        lo, hi = cur+1, len(self.events)-1
        while lo < hi:
            mid = (lo+hi)//2
            if self.events[mid][0] > self.events[cur][1]:
                hi = mid
            else:
                lo = mid+1
        if lo < len(self.events) and self.events[lo][0] > self.events[cur][1]:
            return lo
        elif 0<= lo-1 < len(self.events) and self.events[lo-1][0] > self.events[cur][1]:
            return lo+1
        else:
            return None
    
    def dfs(self, cur: int, k: int) -> int:
        if cur == len(self.events):
            if k>0:
                return 0
            else:
                return 0
        elif k<=0:
            return 0
        elif (cur, k) in self.cache:
            return self.cache[(cur,k)]
        else:
            res = self.INF
            # 1. select current activity
            next_cur = self.search_next(cur)
            if next_cur is None:
                res1 = self.events[cur][2]
            else:
                res1 = self.dfs(next_cur, k-1) + self.events[cur][2]
            # 2, not select current activity
            res2 = self.dfs(cur+1, k)
            res = max(res1, res2)
            self.cache[(cur, k)] = res
            return res
        
    
    def maxValue(self, events: List[List[int]], k: int) -> int:
        events.sort()
        self.events = events
        self.cache = {}
        self.INF = -10**10
        
        res = self.dfs(0,k)
        
        return res
147481