Memory Erosion Optimization

In this problem, you are given two sets of intervals on the real line. The first set consists of m1 start intervals ( [sl_i, sr_i] ) with corresponding contributions ( a_i ) (for ( i=1,2,\dots,m1 )); the second set consists of m2 end intervals ( [el_j, er_j] ) with corresponding contributions ( b_j ) (for ( j=1,2,\dots,m2 )).

A valid segment is defined as a sub‐segment ( [l, r] ) chosen on the number line satisfying the following conditions:

1. Its starting point ( l ) is chosen from one of the start intervals, i.e. ( l \in [sl_i, sr_i] ) for some ( i ).
2. Its ending point ( r ) is chosen from one of the end intervals, i.e. ( r \in [el_j, er_j] ) for some ( j ).
3. It must hold that ( l < r ).

You are to select a collection of segments (say, ( n ) segments) such that:

• The segments are pairwise non–overlapping (two segments ( [l_1, r_1] ) and ( [l_2, r_2] ) are said to overlap if they share an interval of positive length, i.e. if ( [l_1, r_1] \cap [l_2, r_2] ) has length > 0). They may touch, i.e. it is allowed that ( r_1 = l_2 ).
• Each chosen segment is associated with a distinct start interval and a distinct end interval. In other words, no start interval or end interval is used more than once.

For each chosen segment whose start comes from the ( i)-th start interval and end from the ( j)-th end interval, you gain a contribution equal to the segment's length plus the interval contributions, i.e. [ \text{contribution} = (r - l) + a_i + b_j. ]

Since you are free to choose the exact ( l ) and ( r ) (subject to ( l \in [sl_i, sr_i] ) and ( r \in [el_j, er_j] )), the best you can do (if the segment were isolated) is to choose ( l = sl_i ) and ( r = er_j ) for a contribution of [ (er_j - sl_i) + a_i + b_j. ]

However, when selecting more than one segment, you must ensure that if the segments are ordered from left to right (based on their positions on the number line) then for any two consecutive segments ( [l_k, r_k] ) and ( [l_{k+1}, r_{k+1}] ) you have [ r_k \le l_{k+1}. ]

Your task is to choose a set of segments (by pairing start and end intervals) so that the total contribution is maximized. If it is impossible to select any valid segment (i.e. no valid pairing exists), output (-1).

It can be shown that an optimal solution can be obtained by selecting some pairs ( (i,j) ) (each using different start and end intervals) and assigning for each pair ( l = sl_i ) and ( r = er_j ) provided the non–overlap condition ( er_j \le sl_{i'} ) holds between consecutive chosen pairs (after an appropriate reordering).

inputFormat

The input is given as follows:

1. The first line contains two integers, m1 and m2 (the number of start intervals and end intervals respectively).
2. The next m1 lines each contain three integers: sl_i, sr_i, and a_i representing the i-th start interval \( [sl_i, sr_i] \) and its contribution.
3. The following m2 lines each contain three integers: el_j, er_j, and b_j representing the j-th end interval \( [el_j, er_j] \) and its contribution.

outputFormat

Output a single integer representing the maximum total contribution that can be achieved according to the rules, or \(-1\) if no valid segment selection exists.

sample

1 1
1 5 10
4 10 20

39

</p>