题目背景

在 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$ 表示一条蓝色线段。

保证数轴上任意一个整点至多被红色线段覆盖一次。保证数轴上任意一个整点至多被蓝色线段覆盖一次。

输出格式

输出一行一个整数表示答案。

2 3 23
7 18 7
63 71 2
77 86
13 19
63 71

15

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

7

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

13

提示

「样例解释 #1」

如图，选择输入的第 $2$ 条蓝色线段和第 $3$ 条蓝色线段。

第 $2$ 条蓝色线段与第 $1$ 条红色线段有交，交集包含从第 $13$ 个整点到第 $18$ 个整点的所有整点；第 $3$ 条蓝色线段与第 $2$ 条红色线段有交，交集包含从第 $63$ 个整点到第 $71$ 个整点的所有整点。

第 $1$ 条红色线段仅与第 $2$ 条蓝色线段有交，第 $2$ 条红色线段仅与第 $3$ 条蓝色线段有交；和被选择的蓝色线段有交的红色线段权值和为 $9$，方案合法。故答案为 $15$。

「数据范围」

本题采用捆绑测试。

对于 $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$。保证数轴上任意一个整点至多被红色线段覆盖一次。保证数轴上任意一个整点至多被蓝色线段覆盖一次。