Problem Background

At the end of 2022, the pandemic confined most students of a well-known school in the northwest to their homes for online classes. An, a student, was unaware that his confrontation with his Chinese teacher had already begun silently—he slept through every morning reading and Chinese class.

An was used to getting up, dressing, and sleeping in front of the camera, which only captured half of his shoulder. Even if the camera was forcibly turned on, it wouldn't expose the fact that he was sleeping, and no teacher had ever forced it open. On this extraordinary morning, the Chinese teacher turned on his camera. It was time for morning reading, and he was awakened by the teacher's caring voice, but it was too late, the teacher was already furious. An decided to pretend that the network was lagging to calm the teacher's anger.

The teacher, enraged! After An woke up, she would call his real name during certain periods, and wait for his response during the rest. Meanwhile, An needed to create a network lag illusion. He could check his equipment or call the teacher during certain periods, and remain still or randomly flash in the frame during others. His actions during these periods are called performances. Your task is to help An maximize his performance time without angering the teacher.

Because An is too abstract, the original problem statement was also influenced and became abstract. Here, you are only shown the formalized problem statement.

Problem Description

Given three positive integers \( n, m, k \) and two sets of segments. The first set of segments has weights, totaling \( n \) segments, which are red; the second set of segments has no weights, totaling \( m \) segments, which are blue. These segments are located on the same number line.

• A red segment is represented by three positive integers \( l, r, w \), covering from the \( l \)-th integer point to the \( r \)-th integer point on the number line with a weight of \( w \). Ensure that any integer point on the number line is covered by at most one red segment.

• A blue segment is represented by two positive integers \( L, R \), covering from the \( L \)-th integer point to the \( R \)-th integer point on the number line with no weight. Ensure 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) \), it is considered that these two segments intersect, including all integer points from the \( \max(l_0, L_0) \)-th to the \( \min(r_0, R_0) \)-th, totaling \( \min(r_0, R_0) - \max(l_0, L_0) + 1 \) integer points. You can choose some blue segments, and a valid selection scheme must meet the following conditions:

• Each given red segment intersects with at most one of the blue segments you choose.

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

When the selection scheme is valid, what is the maximum number of integer points that can be included in the intersections of the blue segments you choose with all red segments?

Input Format

The first line inputs three positive integers \( n, m, k \).

The next \( n \) lines, the \( i \)-th line inputs three positive integers \( l_i, r_i, w_i \) representing a red segment.

The next \( m \) lines, the \( i \)-th line inputs two positive integers \( L_i, R_i \) representing a blue segment.

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

Output Format

Output one line with one integer representing the answer.

Sample Input and Output

Input Sample #1

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

Output Sample #1

15

Input Sample #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

Output Sample #2

7

Input Sample #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

Output Sample #3

13

Notes

「Sample Explanation #1」

As shown in the figure, select the second and third blue segments from the input.

The second blue segment intersects with the first red segment, including all integer points from the 13th to the 18th; the third blue segment intersects with the second red segment, including all integer points from the 63rd to the 71st.

The first red segment intersects only with the second blue segment, and the second red segment intersects only with the third blue segment; the sum of the weights of the red segments that intersect with the chosen blue segments is 9, making the scheme valid. Hence, the answer is 15.

「Data Range」

This problem uses bundled testing.

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

见题面 Input 部分

见题面 Output 部分