In the year 9012, the aviation base in City Z plans to hold an aerobatic flight performance. The performance venue can be viewed as a two-dimensional Cartesian coordinate system, where the x-coordinate represents the horizontal position and the y-coordinate represents the flight altitude.

In the initial plan, $n$ aircraft will first fly to the starting point $x = x_{st}$, where the $i$-th aircraft has an altitude of $y_{i,0}$ at the start. Their target is the destination $x = x_{ed}$, where the $i$-th aircraft should have an altitude of $y_{i,1}$. Therefore, each aircraft can be viewed as a point in the coordinate system, and its flight path is a line segment starting from $(x_{st}, y_{i,0})$ and ending at $(x_{ed}, y_{i,1})$, as shown in the figure below.

These $n$ aircraft depart simultaneously and maintain a constant ground speed. Therefore, for any two intersecting flight paths (line segments), the corresponding two aircraft will inevitably reach the intersection point at the same time—this is the moment they perform their aerobatic stunt. They will deflect their wings to perform a "brushing past" stunt at an extremely close distance, and then continue on their respective paths.

The aviation base has recently researched a new stunt called "directional exchange." When two aircraft reach an intersection point, the one that was previously descending immediately switches to an ascending maneuver, while the one that was previously ascending performs a loop. The two aircraft pass the intersection point one above the other, belly-to-belly, at an extremely close distance, and then swap their subsequent flight paths.

We do not need to concern ourselves with how these stunts are physically achieved. The aircraft are still treated as points. Under the two types of stunts, the changes in the flight paths are shown in the figure below (where $y'_{i,1}$ represents the new altitude of the $i$-th aircraft at the destination after swapping paths). It is easy to see that a "directional exchange" causes their paths to become a broken line and maintains their relative order in the y-coordinates, while a "brushing past" changes their relative order in the y-coordinates.

Now, the guest delegation watching the performance has put forward a strict requirement: at the destination $x = x_{ed}$, the relative order of the $n$ aircraft when sorted by altitude must be consistent with their relative order at $x = x_{st}$. The guest delegation has also assigned difficulty coefficients $a$ and $b$ to the "directional exchange" and "brushing past" stunts, respectively. Each "directional exchange" stunt earns $a$ points, and each "brushing past" stunt earns $b$ points.

In addition, there are $k$ members in the guest delegation. The $j$-th member stays in a hot air balloon at position $(p_j, q_j)$ with an observation range $r_j$, and can observe all stunts within the region $|x - p_j| + |y - q_j| \le r_j$. If a stunt at an intersection point is observed by one or more guests, an additional $c$ points are awarded. Note that regardless of whether a stunt is observed, it still earns $a$ or $b$ points.

The figure below shows an arrangement for the 4 flight paths and 4 intersection points in the first figure of this problem that satisfies the requirements, including 2 "directional exchange" stunts and 2 "brushing past" stunts, with 3 stunts being observed, resulting in a score of $2a + 2b + 3c$. For ease of observation, the figure shows the intersection points of the "directional exchange" stunts slightly separated.

In this scenario, you have become the planner for the City Z aviation base. You can decide whether to perform a "directional exchange" or a "brushing past" at each intersection point. You are required to calculate the minimum and maximum possible scores for the entire aerobatic performance while ensuring the guest delegation's requirements are met.

Input

Read data from the file aerobatics.in.

The first line contains six non-negative integers $n, a, b, c, x_{st}, x_{ed}$, representing the total number of flight paths (line segments), the score for a "directional exchange" stunt, the score for a "brushing past" stunt, the additional bonus for an observed stunt, the x-coordinate of the starting point, and the x-coordinate of the destination, respectively.

The second line contains $n$ non-negative integers $y_{i,0}$, where the $i$-th number represents the starting y-coordinate of the $i$-th flight path, guaranteed to be given in ascending order, i.e., $y_{i,0} < y_{i+1,0}$.

The third line contains $n$ non-negative integers $y_{i,1}$, where the $i$-th number represents the destination y-coordinate of the $i$-th flight path.

The fourth line contains a non-negative integer $k$, representing the number of guests.

The next $k$ lines each contain three non-negative integers $p_j, q_j, r_j$, representing the x-coordinate, y-coordinate, and observation range of the $j$-th guest, respectively.

The input data also has some restrictions on the total number of intersection points for all flight paths (line segments) between the lines $x = x_{st}$ and $x = x_{ed}$, see "Constraints" for details.

Output

Output to the file aerobatics.out.

Output a single line containing two integers, representing the minimum and maximum possible scores for the entire aerobatic performance, separated by a space.

Examples

Input 1

4 1 2 3 1 6
1 2 3 4
4 1 3 2
2
3 3 1
5 2 2

Output 1

13 15

Note 1

The flight paths in this example are the same as those depicted in the problem description, only the positions of the guests are slightly different. The minimum score performance plan is to use the "directional exchange" stunt at all intersection points, scoring $4a + 3c = 13$. The maximum score performance plan is consistent with the situation depicted in the problem description, scoring $2a + 2b + 3c = 15$.

Input 2

10 73 28 13 0 100
2 9 16 25 29 34 43 46 52 58
8 25 35 52 41 5 16 3 19 48
5
46 40 1
37 27 5
67 34 1
65 28 4
29 38 1

Output 2

989 1619

Constraints

Figure 1. Flight paths of aircraft as line segments from (x_st, y_i,0) to (x_ed, y_i,1).