该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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