Lunar New Year and Red Envelopes
Contest: Codeforces Round 536 (Div. 2)
Difficulty rating: 2100
Tags: data structures, dp

Lunar New Year is approaching, and Bob is going to receive some red envelopes with countless money! But collecting money from red envelopes is a time-consuming process itself.

Let's describe this problem in a mathematical way. Consider a timeline from time $$$1$$$ to $$$n$$$. The $$$i$$$-th red envelope will be available from time $$$s_i$$$ to $$$t_i$$$, inclusive, and contain $$$w_i$$$ coins. If Bob chooses to collect the coins in the $$$i$$$-th red envelope, he can do it only in an integer point of time between $$$s_i$$$ and $$$t_i$$$, inclusive, and he can't collect any more envelopes until time $$$d_i$$$ (inclusive) after that. Here $$$s_i \leq t_i \leq d_i$$$ holds.

Bob is a greedy man, he collects coins greedily — whenever he can collect coins at some integer time $$$x$$$, he collects the available red envelope with the maximum number of coins. If there are multiple envelopes with the same maximum number of coins, Bob would choose the one whose parameter $$$d$$$ is the largest. If there are still multiple choices, Bob will choose one from them randomly.

However, Alice — his daughter — doesn't want her father to get too many coins. She could disturb Bob at no more than $$$m$$$ integer time moments. If Alice decides to disturb Bob at time $$$x$$$, he could not do anything at time $$$x$$$ and resumes his usual strategy at the time $$$x + 1$$$ (inclusive), which may lead to missing some red envelopes.

Calculate the minimum number of coins Bob would get if Alice disturbs him optimally.

Input format:
The first line contains three non-negative integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \leq n \leq 10^5$$$, $$$0 \leq m \leq 200$$$, $$$1 \leq k \leq 10^5$$$), denoting the length of the timeline, the number of times Alice can disturb Bob and the total number of red envelopes, respectively.

The following $$$k$$$ lines describe those $$$k$$$ red envelopes. The $$$i$$$-th line contains four positive integers $$$s_i$$$, $$$t_i$$$, $$$d_i$$$ and $$$w_i$$$ ($$$1 \leq s_i \leq t_i \leq d_i \leq n$$$, $$$1 \leq w_i \leq 10^9$$$) — the time segment when the $$$i$$$-th envelope is available, the time moment Bob can continue collecting after collecting the $$$i$$$-th envelope, and the number of coins in this envelope, respectively.

Output format:
Output one integer — the minimum number of coins Bob would get if Alice disturbs him optimally.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first sample, Alice has no chance to disturb Bob. Therefore Bob will collect the coins in the red envelopes at time $$$1$$$ and $$$5$$$, collecting $$$13$$$ coins in total.

In the second sample, Alice should disturb Bob at time $$$1$$$. Therefore Bob skips the first envelope, collects the second one and can not do anything after that. So the answer is $$$2$$$.

Example input:
5 0 2
1 3 4 5
2 5 5 8

Example output:
13

Example input:
10 1 6
1 1 2 4
2 2 6 2
3 3 3 3
4 4 4 5
5 5 5 7
6 6 6 9

Example output:
2

Editorial:
Yes, this is where Alice shows up and ... probably the problem is not related to Game Theory. Let's divide the problem into two parts: The first is to obtain the maximum coins Bob can get from time points $$$1$$$ to $$$n$$$, and the second is to decide when to disturb Bob.
For the first part, we apply event sorting to those time segments. After that, we use a set with a sweep line to deal with it. Whenever we meet a start or a terminate of one red envelope, we add this into the set or remove that from the set. Note that you need to use multiset, since there can be multiple red envelopes with same $$$d$$$ and $$$w$$$.
For the second part, we apply dynamic programming since $$$m$$$ is relatively small. Let $$$f[i][j]$$$ denote that the minimum coins Bob gets when we only consider the timeline from $$$1$$$ to $$$i$$$ and Alice disturbs Bob for $$$j$$$ times. The transition is trivial and you can take a look at it in the code.
Time complexity: $$$\mathcal{O}((n + k) \log k + nm)$$$