<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>




// STL C++
#include <bits/stdc++.h>
using namespace std;

// GNU C++
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;

// #include <ext/rope> //header with rope
// using namespace __gnu_cxx; //namespace with rope and some additional stuff


//int64_t // uint64_t
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;
typedef pair<ll, pii> plii;


typedef vector<int> vi;
typedef vector<ld> vld;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vb> vvb;
typedef vector<vc> vvc;
typedef vector<vs> vvs;

#define tcT template<class T
#define tcTU tcT, class U

#define FORK(i, a, b, k) for (int i=a; i<(b); i+=k)
#define FOR(i, a, b) FORK(i, a, b, 1)
#define F0R(i, a) FOR(i, 0, a)
#define ROFK(i, N, a, k) for (int i = (N)-1; i >= (a); i-=k)
#define ROF(i, N, a) ROFK(i, N, a, 1)
#define R0F(i, N) ROF(i, N, 0)
#define trav(x, arr) for (auto& x : arr)
#define uid(a, b) uniform_int_distribution<ll>(a, b)(rng)

#define sz(x) (int)(x).size()
#define all(v)  v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()

#define lwb(c, x)  distance((c).begin(), lower_bound(all(c), (x))) // first elt >= 
#define lbg(c, x)  distance((c).begin(), lower_bound(all(c), (x), greater{}))
#define upb(c, x)  distance((c).begin(), upper_bound(all(c), (x))) // fist elt >
#define ubg(c, x)  distance((c).begin(), upper_bound(all(c), (x), greater{}))

#define argmax(c)  distance((c).begin(), max_element(all(c)) )
#define argmin(c)  distance((c).begin(), min_element(all(c)) )

#define not_in(c, x)  c.find(x) == c.end()
#define  is_in(c, x)  c.find(x) != c.end()


#define f first
#define s second

#define coutfix(n) std::setprecision(n) << std::fixed 
#define trailfill(n, c) std::left << std::setfill(c) << std::setw(n);
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL)
#define endl '\n'

#define pq priority_queue


template<class T> using ordered_set      = tree<T,  null_type, less<T>,        rb_tree_tag, tree_order_statistics_node_update> ;
template<class T> using ordered_multiset = tree<T,  null_type, less_equal<T>,  rb_tree_tag, tree_order_statistics_node_update> ; //erase with oset.erase(oset.upper_bound(value))

template<class T> using minpq = pq<T, vector<T>, greater<T>>;
// #define pqnode(comp) template<class T> pq<T, vector<T>, decltype( comp ) > pqvar( comp );

template<class T> using vset  = vector<set<T>>;
template<class T, class U> using vmap  = vector<map<T, U>>;


template<typename T> bool chkmax(T &m, const T q) { return m < q ? (m = q, true) : false; }
template<typename T> bool chkmin(T &m, const T q) { return m > q ? (m = q, true) : false; }

template<typename T> void unique( vector<T> &arr ) { sort(all(arr));  arr.erase( unique( all(arr) ), arr.end() );  }


template<typename T> ostream& operator<<(ostream& out, vector<T> &a) {for (auto &x : a) out << x << ' '; return out;};
template<typename T> istream& operator>>(istream& cin, vector<T> &a) {for (auto &x : a) cin >> x;        return cin;};
template<typename T1, typename T2> ostream& operator<<(ostream& out, vector<pair<T1, T2>> &a) {for (auto &x : a) out << x.f << ' ' << x.s << endl; return out;};
template<typename T1, typename T2> istream& operator>>(istream& cin, vector<pair<T1, T2>> &a) {for (auto &x : a) cin >> x.f >> x.s;  return cin;};

template<typename T> ostream& operator<<(ostream& out, set<T> &a) {for (auto &x : a) out << x << ' '; return out;};




ll const MOD = 1e9 + 7LL;
ll const modInv2 = 500000004LL;
ll const modInv4 = 250000002LL;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxint = numeric_limits<ll>::max() - 100ll;
const ll minint = numeric_limits<ll>::min() + 100ll;




tcTU> T binMin_fIncrease(T lo, T hi, U f) {
	++hi; assert(lo <= hi); // assuming f is increasing
	while (lo < hi) { // find first index such that f is true 
		T mid = lo+(hi-lo)/2;
		f(mid) ? hi = mid : lo = mid+1; 
	} 
	return lo;
}

tcTU> T binMax_fIncrease(T lo, T hi, U f) {
	T ans = minint;
	++hi; assert(lo <= hi); // assuming f is increasing
	while (lo <= hi) { // find last index such that f is true 
		T mid = lo+(hi-lo)/2;
		f(mid) ? ( lo = mid + 1, chkmax(ans, mid)  ): (hi = mid - 1) ; 
	} 
	return ans;
}




tcTU> T lstTrue(T lo, T hi, U f) {
	--lo; assert(lo <= hi); // assuming f is decreasing
	while (lo < hi) { // find first index such that f is true 
		T mid = lo+(hi-lo+1)/2;
		f(mid) ? lo = mid : hi = mid-1;
	} 
	return lo;
}




void debug(){ /*break point*/  }
void YES(){ cout << "Yes" << endl;  }
void NO() { cout << "No"  << endl;  }








class Solution {
public:
    int maxValue(vector<vector<int>>& events, int k) {
        
        int n = sz(events); 
        sort(all(events));

        vvi dp(n+1, vi(k+1, -1));

        map<int, int> _search;
        FOR(i, 0, n) if( not_in(_search, events[i][0]  )  )  {
            _search[ events[i][0]  ] = i;
        }


        auto recu = [&](auto&& self,  int i, int kk) -> int{

            if(i >= n || kk >= k ){return 0;}

            if(dp[i][kk] != -1){return dp[i][kk];}

            int idx = n;

            // for(idx = i + 1; idx < n; idx++)
            // 	if(events[idx][0] > events[i][1])
            // 		break;

            auto it = _search.upper_bound( events[i][1] );
            if(it != _search.end()){idx = it->s;}

            return dp[i][kk] = max( self(self, i+1, kk   ), self(self, idx, kk+1) + events[i][2] ) ;
        };

        return recu(recu, 0, 0);

    }
};


140121