Aerobatics Performance Scoring

In the year \(9012\), the Z city aerospace base is preparing a breathtaking aerobatics show. The performance field is modeled as a 2D Cartesian coordinate system: the \(x\)-axis represents the horizontal position while the \(y\)-axis denotes the flying altitude. Initially, \(n\) airplanes start at \(x = x_{st}\). The \(i\)th airplane starts at altitude \(y_{i,0}\) and is scheduled to reach altitude \(y_{i,1}\) at \(x = x_{ed}\). Thus, each airplane’s planned flight is the straight line segment from \((x_{st}, y_{i,0})\) to \((x_{ed}, y_{i,1})\).

Two airplanes’ flight paths may cross. At each crossing point, the pilot can choose one of two stunts:

• Opposite Exchange (score \(a\)): When the two planes meet, the plane which was descending immediately starts climbing and the one that was climbing performs a flip. They pass the intersection extremely close to each other and continue on their originally planned routes. In particular, the relative vertical order of the two airplanes remains unchanged.
• Scrape Past (score \(b\)): When the two planes meet, they execute a maneuver in which they pass by each other in opposite directions, and then exchange the remainder of their flight paths. This maneuver reverses the relative vertical order of the two airplanes.

There is an additional twist. The audience has demanded that the relative vertical order at the endpoint \(x=x_{ed}\) must be exactly the same as the order at \(x=x_{st}\) (when the airplanes took off). Completing a stunt (regardless of type) at an intersection also yields an extra bonus if observed. There are \(k\) balloon observers. The \(i\)th observer is stationed at \((p_i,q_i)\) and can observe any stunt that occurs within his/her Manhattan distance radius \(r_i\); that is, any point \((x,y)\) satisfying

[ |x-p_i|+|y-q_i| \le r_i. ]

If one or more observers see the stunt at an intersection, an extra bonus of \(c\) is awarded (in addition to the base score \(a\) or \(b\)). Note that the bonus is awarded independently of the type of stunt and the stunt’s score is earned regardless of whether it is observed.

Flight adjustments – When two airplanes fly along crossing trajectories, a decision must be made at the intersection point: choosing Opposite Exchange leaves the pair’s vertical order unchanged, while choosing Scrape Past swaps their endpoints (and hence eventually reverses their order). However, to meet the audience’s requirement (that the final \(y\)-order remains the same as the initial order), the overall effect of all the stunts must be to transform the initial assignment of endpoint altitudes into the sorted (non‐decreasing) order. In other words, if the initial list of endpoint altitudes (in the order of increasing \(y_{i,0}\)) is \(E = [y_{1,1},y_{2,1},\dots,y_{n,1}]\), then after performing all stunts the final endpoints must become \(E' = \text{sort}(E)\.

It turns out that every crossing occurs between a unique pair of airplanes \(i,j\) (with \(i<j\) when the planes are sorted in increasing order of \(y_{i,0}\)) for which
\(y_{i,1} > y_{j,1}\). At each such intersection, you can choose either:

• Performing Opposite Exchange yields a score of \(a + \text{bonus}\) (where the bonus is \(c\) if the intersection is observed, else 0) and leaves the pair’s order unchanged.
• Performing Scrape Past gives a score of \(b + \text{bonus}\) and swaps the endpoints between the two planes.

Because swapping affects the final distribution of endpoint altitudes, there is a minimum number of swaps required to rearrange \(E\) into sorted order. In fact, if we denote this minimum number as \(X_{min}\), then the total number of crossings \(M\) (i.e. the number of inversion pairs) must have the same parity as \(X_{min}\) and the possible total number of swaps executed can only be \(X = X_{min} + 2t\) for some nonnegative integer \(t\) with \(X \le M\).

Your task is: Given \(n\) airplanes, their starting and planned endpoint altitudes, the performance horizontal coordinates \(x_{st}\) and \(x_{ed}\), the scores \(a\), \(b\), bonus \(c\); and \(k\) observers (with positions and radii), calculate the minimum and maximum total score that can be achieved by choosing the stunt type at each crossing so that the final vertical order equals the initial one.

Intersection details: For a crossing between airplanes \(i\) and \(j\) (with \(iy_{j,1}\)), let the flight of airplane \(i\) be given by
\( x=x_{st}+t(x_{ed}-x_{st}),\quad y=y_{i,0}+t(y_{i,1}-y_{i,0}),\quad 0\le t\le 1,\)

and similarly for airplane \(j\). Their intersection occurs at a parameter

[ t = \frac{y_{j,0}-y_{i,0}}{(y_{i,1}-y_{i,0})-(y_{j,1}-y_{j,0])}. ]

Using this \(t\), the intersection point is \((x, y)\) with

[ x=x_{st}+t(x_{ed}-x_{st}),\quad y=y_{i,0}+t(y_{i,1}-y_{i,0]). ]

An intersection’s bonus is \(c\) if at least one observer satisfies
\(|x-p_i|+|y-q_i| \le r_i\) for that intersection point; otherwise the bonus is 0.

inputFormat

The first line contains seven integers: \(n\), \(k\), \(x_{st}\), \(x_{ed}\), \(a\), \(b\), \(c\) (number of airplanes, number of observers, starting and ending \(x\)-coordinates, the score for Opposite Exchange, the score for Scrape Past, and the bonus score, respectively).

The second line contains \(n\) integers: \(y_{1,0}, y_{2,0}, \dots, y_{n,0}\) — the starting altitudes of the airplanes.

The third line contains \(n\) integers: \(y_{1,1}, y_{2,1}, \dots, y_{n,1}\) — the planned endpoint altitudes.

Then \(k\) lines follow, each containing three integers: \(p_i\), \(q_i\), \(r_i\), representing the \(i\)th observer’s position and observation radius.

Note: The airplanes are not necessarily given in order of increasing \(y_{i,0}\); you should sort them by their starting altitude. The final required order at \(x_{ed}\) must match the order at \(x_{st}\) (i.e. the sorted order by \(y_{i,0}\)).

outputFormat

Output two integers separated by a space: the minimum and maximum total scores that can be achieved subject to the final order constraint.

sample

2 0 0 10 1 2 5
1 2
5 3

2 2