Maximum Intersection of Red and Blue Segments Under a Weight Constraint

You are given three positive integers \(n\), \(m\), and \(k\) and two sets of segments on a number line. The first set consists of \(n\) red segments, each with a weight, while the second set consists of \(m\) blue segments without weights. It is guaranteed that no integer point on the number line is covered by more than one red segment, and similarly, no integer point is covered by more than one blue segment.

A red segment is described by three positive integers \(l, r, w\), meaning it covers all integer points from \(l\) to \(r\) (inclusive) with weight \(w\). A blue segment is described by two positive integers \(L, R\), meaning it covers integer points from \(L\) to \(R\) (inclusive).

We say that a red segment \([l_0, r_0]\) and a blue segment \([L_0, R_0]\) intersect if \[ \max(l_0,L_0) \le \min(r_0,R_0), \] and in that case the intersection covers all integer points from \(\max(l_0,L_0)\) to \(\min(r_0,R_0)\) (inclusive).

You may choose some blue segments subject to the following conditions:

• Each red segment intersects with at most one of the blue segments you choose.
• If a red segment does intersect with one of your chosen blue segments then the sum of the weights of all such red segments (i.e. all red segments that intersect with any chosen blue segment) does not exceed \(k\).

When a choice is legal the score is the total number of integer points that lie in the intersection between each red segment and the unique blue segment it intersects. Compute the maximum possible score.

Observation: Since red segments do not overlap with each other, the legality condition forces that for each red segment, you may consider to "activate" it by picking one blue segment that intersects it. If a red segment is activated then its entire contribution is the length of the intersection with the chosen blue segment, and its weight is counted towards the overall cost. Note that if a red segment intersects more than one blue segment, you can choose the one that gives the maximum intersection length.

This allows the following reformulation: For each red segment \(i\) with interval \([l_i,r_i]\) and weight \(w_i\), let its potential contribution be defined as:

[ val_i = \max_{\substack{\text{blue segment }[L,R]\[l_i,r_i] \cap [L,R] \neq \emptyset}} {\min(r_i,R)-\max(l_i,L)+1} ]

If no blue segment intersects red segment \(i\), define \(val_i=0\). Then the problem becomes a standard 0/1 knapsack: choose a subset of red segments (activate them) so that the total weight does not exceed \(k\), and maximize the sum of \(val_i\). A red segment can only be activated if there exists at least one blue segment that intersects it; if multiple blue segments intersect it, you get to pick the one that gives the best (largest) intersection length.

Input and Output descriptions below follow.

inputFormat

The first line contains three space-separated integers: n, m and k.

The next n lines each contain three space-separated positive integers l, r, w representing a red segment covering points from l to r with weight w.

The next m lines each contain two space-separated positive integers L, R representing a blue segment covering points from L to R.

outputFormat

Output a single integer representing the maximum total number of integer points in the intersections between red segments and the blue segment that activates them under the given constraint.

sample

2 2 3
2 10 2
12 15 2
1 11
14 20

9