【MX-J1-T4】『FLA - III』Wrestle
题目背景
原题链接：<https://oier.team/problems/J1D>。
---
在 2022 年末，疫情将西北某不知名知名学校的大多数学生关在家中上网课，安同学还不知道，他和语文老师的对决已然悄无声息地开始了——他每天早读和语文课都直接睡过去了。
安同学习惯起来穿好衣服、面对摄像头睡觉，摄像头只能拍到他的半个肩膀，就算被强制打开也不会暴露他在睡觉的事实，而且从来没有老师强制打开他的摄像头。而这个不凡的早晨，语文老师打开了他的摄像头，现在是早读时间，他在朦胧中被老师的关爱声叫醒，可惜为时已晚，老师已经愤怒。安同学决定假装网络卡顿，平复老师愤怒的心情。
老师，愤怒了！在安同学醒来后的某些时间段，她要呼叫他的真名，其余时间等他应答。与此同时安同学要打造网卡的假象，他可以在某些时间段内检查设备或者呼叫老师，其余时间静止或随机在画面中闪现，他在这些时间段内的行为称为表演。你的任务是帮助安同学在不激怒老师的情况下最大化表演时间。
因为安同学实在是太抽象了，原始题面受他影响变得也很抽象，这里只有形式化题面给你看。
题目描述
给定三个正整数 $n,m,k$ 和两组线段。第一组线段有权值，共 $n$ 条，是**红色**的；第二组线段没有权值，共 $m$ 条，是**蓝色**的。这些线段位于同一个数轴。
- 使用 $l,r,w$ 三个正整数表示一条从数轴上第 $l$ 个整点覆盖到第 $r$ 个整点，权值为 $w$ 的红色线段。**保证数轴上任意一个整点至多被红色线段覆盖一次。**
- 使用 $L,R$ 两个正整数表示一条从数轴上第 $L$ 个整点覆盖到第 $R$ 个整点，没有权值的蓝色线段。**保证数轴上任意一个整点至多被蓝色线段覆盖一次。**
如果一条红色线段从第 $l_0$ 个整点覆盖到第 $r_0$ 个整点，一条蓝色线段从第 $L_0$ 个整点覆盖到第 $R_0$ 个整点且 $\max(l_0,L_0) \leq \min(r_0,R_0)$，就认为这两条线段有交集，交集包含从第 $\max(l_0,L_0)$ 个整点到第 $\min(r_0,R_0)$ 个整点的全部 $\min(r_0,R_0)-\max(l_0,L_0)+1$ 个整点。你可以选择一些蓝色线段，一种合法的选择方案必须符合以下条件：
- 题目给定的每条红色线段至多与你选择的 $1$ 条蓝色线段有交集。
- 所有和**你选择的蓝色线段**有交集的红色线段权值之和不超过 $k$。
选择方案合法时，**你选择的蓝色线段**和**所有红色线段**的交集至多能包含多少个整点？
输入输出格式
输入格式
第一行输入三个正整数 $n,m,k$。
接下来 $n$ 行，第 $i$ 行输入三个正整数 $l_i,r_i,w_i$ 表示一条红色线段。
接下来 $m$ 行，第 $i$ 行输入两个正整数 $L_i,R_i$ 表示一条蓝色线段。
**保证数轴上任意一个整点至多被红色线段覆盖一次。保证数轴上任意一个整点至多被蓝色线段覆盖一次。**
输出格式
输出一行一个整数表示答案。
输入输出样例
输入样例 #1
2 3 23
7 18 7
63 71 2
77 86
13 19
63 71
输出样例 #1
15
输入样例 #2
4 5 7
59 65 7
39 42 1
43 51 2
19 33 2
14 25
71 81
6 11
59 69
83 92
输出样例 #2
7
输入样例 #3
4 8 45
80 94 22
60 67 2
35 44 45
7 14 5
82 86
2 3
58 63
48 50
73 80
25 45
11 19
93 94
输出样例 #3
13
说明
**「样例解释 #1」**
如图，选择输入的第 $2$ 条蓝色线段和第 $3$ 条蓝色线段。
第 $2$ 条蓝色线段与第 $1$ 条红色线段有交，交集包含从第 $13$ 个整点到第 $18$ 个整点的所有整点；第 $3$ 条蓝色线段与第 $2$ 条红色线段有交，交集包含从第 $63$ 个整点到第 $71$ 个整点的所有整点。
第 $1$ 条红色线段仅与第 $2$ 条蓝色线段有交，第 $2$ 条红色线段仅与第 $3$ 条蓝色线段有交；和被选择的蓝色线段有交的红色线段权值和为 $9$，方案合法。故答案为 $15$。
**「数据范围」**
**本题采用捆绑测试。**
|Subtask|$n \leq$|$m \leq$|$k \leq$|$l_i,r_i,L_i,R_i \leq$|分值|
|:-:|:-:|:-:|:-:|:-:|:-:|
|**#1**|$10$|$10$|$50$|$100$|$20$|
|**#2**|$200$|$200$|$200$|$10^5$|$30$|
|**#3**|$5000$|$5000$|$5000$|$10^9$|$30$|
|**#4**|$2 \times 10^5$|$5000$|$5000$|$10^9$|$20$|
对于 $100\%$ 的数据，$1 \leq n \leq 2 \times 10^5$，$1 \leq m,k \leq 5000$，$1 \leq l_i,r_i,L_i,R_i \leq 10^9$，$1 \leq w_i \leq k$，$l_i < r_i$，$L_i < R_i$。**保证数轴上任意一个整点至多被红色线段覆盖一次。保证数轴上任意一个整点至多被蓝色线段覆盖一次。**