Background

Original problem link: https://oier.team/problems/J1D.

At the end of 2022, the pandemic kept most students of a certain well-known (yet somehow unknown) school in Northwest China at home for online classes. Student An still did not know that his showdown with the Chinese teacher had already begun quietly—he slept through both morning reading and Chinese class every day.

Student An was used to getting up, getting dressed, and sleeping in front of the camera. The camera could only capture half of his shoulder, so even if it was forced on, it would not reveal that he was sleeping. Also, no teacher had ever forced him to turn on his camera. But on this unusual morning, the Chinese teacher turned on his camera. It was morning reading time. He was woken up in a daze by the teacher’s “caring” voice, but it was too late—the teacher was already angry. Student An decided to pretend that his network was lagging, to calm the teacher down.

The teacher was angry. During certain time intervals after Student An woke up, she would call his real name; during the other time intervals, she would wait for his response. At the same time, Student An needed to create the illusion of network lag: during certain time intervals, he could check devices or call the teacher; during the other time intervals, he would stay still or randomly flash in the video. His actions during those time intervals are called a performance. Your task is to help Student An maximize the performance time without angering the teacher.

Because Student An is really too “abstract,” the original statement was also made very “abstract” by him. Here, only the formal statement is provided.

Problem Description

You are given three positive integers $n, m, k$ and two sets of segments. The first set has weights and contains $n$ red segments; the second set has no weights and contains $m$ blue segments. These segments lie on the same number line.

• Use three positive integers $l, r, w$ to represent a red segment that covers from the $l$-th integer point on the number line to the $r$-th integer point, with weight $w$. It is guaranteed that any integer point on the number line is covered by at most one red segment.

• Use two positive integers $L, R$ to represent a blue segment that covers from the $L$-th integer point on the number line to the $R$-th integer point, with no weight. It is guaranteed that any integer point on the number line is covered by at most one blue segment.

If a red segment covers from the $l_0$-th integer point to the $r_0$-th integer point, and a blue segment covers from the $L_0$-th integer point to the $R_0$-th integer point, and $\max(l_0, L_0) \leq \min(r_0, R_0)$, then these two segments are considered to intersect. Their intersection contains all $\min(r_0, R_0) - \max(l_0, L_0) + 1$ integer points from the $\max(l_0, L_0)$-th integer point to the $\min(r_0, R_0)$-th integer point.

You may choose some blue segments. A selection is legal if and only if it satisfies all of the following conditions:

• Each red segment given in the input intersects with at most $1$ blue segment that you choose.

• The sum of weights of all red segments that intersect with the blue segments you choose does not exceed $k$.

When the selection is legal, what is the maximum possible number of integer points that can be contained in the intersection between the blue segments you choose and all red segments?

Input Format

The first line contains three positive integers $n, m, k$.

The next $n$ lines: the $i$-th line contains three positive integers $l_i, r_i, w_i$, describing a red segment.

The next $m$ lines: the $i$-th line contains two positive integers $L_i, R_i$, describing a blue segment.

It is guaranteed that any integer point on the number line is covered by at most one red segment. It is guaranteed that any integer point on the number line is covered by at most one blue segment.

Output Format

Output one integer in a single line, representing the answer.

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

Hint

Sample Explanation #1

As shown in the figure, choose the $2$-nd and the $3$-rd blue segments in the input.

The $2$-nd blue segment intersects with the $1$-st red segment, and the intersection contains all integer points from the $13$-th to the $18$-th; the $3$-rd blue segment intersects with the $2$-nd red segment, and the intersection contains all integer points from the $63$-th to the $71$-th.

The $1$-st red segment intersects only with the $2$-nd blue segment, and the $2$-nd red segment intersects only with the $3$-rd blue segment. The total weight of red segments that intersect with the selected blue segments is $9$, so the selection is legal. Therefore, the answer is $15$.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $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$. It is guaranteed that any integer point on the number line is covered by at most one red segment. It is guaranteed that any integer point on the number line is covered by at most one blue segment.

Translated by ChatGPT 5