Description

Consider a game where the game map can be viewed as the first and fourth quadrants of a Cartesian coordinate plane.

In the first quadrant, there will be $n$ objects. An object can be a point, or a line segment parallel to the $y$-axis. When an object appears, the point on the object closest to the $x$-axis and the point farthest from the $x$-axis are called the lowest point and the highest point of the object, respectively. If the object is a point, then its lowest point and highest point are the same.

The $i$-th object appears at time $t_i$. Its lowest point is $(x_i,l_i)$ and its highest point is $(x_i,r_i)$. It then moves at constant speed $v_i$ along the negative direction of the $y$-axis.

The player may mark any integer point on the positive half-axis of the $x$-axis (if this position has already been marked, then this mark does not affect the previous marks), which is called a mark operation. The player may also cancel a mark, which is called a cancel-mark operation. Any number of operations can be done at the same time. It is known that the player performed $m$ pairs of operations. The position of the $i$-th pair is $p_i$, and the times of the mark operation and the cancel-mark operation are $a_i$ and $b_i$, respectively.

Each object initially is in the normal state.

If at some time, for an object, a mark operation happens at a position whose distance to the object’s lowest point is at most $d_0$, and the object is in the normal state, then a scoring event occurs, and the event parameter $d$ is the distance between the operation position and the object’s lowest point. If multiple mark operations satisfy the condition, choose the one that makes $d$ minimal; if there are still multiple, choose the one whose position is closest to the origin. It is guaranteed that the chosen operation is unique. Then, for this object, if it is a point, it disappears; otherwise, it will be marked by this operation and becomes in the marked state. Note that one operation can affect multiple objects, while one object will not be marked by multiple operations.

If at some time, for an object, a cancel-mark operation happens at a position whose distance to the object’s highest point is at most $d_0$, and the object is marked by the corresponding mark operation, then a scoring event also occurs, and the event parameter $d$ is the distance between the operation position and the object’s highest point. Then, the object disappears.

If at some time, an object in the normal state has its lowest point reach the fourth quadrant (note that points on the axes do not belong to any quadrant), or an object in the marked state has its corresponding mark canceled and no scoring event happens due to this cancel-mark operation, then a miss event occurs. Then, the object disappears.

When a scoring event with parameter $d$ occurs, the player gains a base score of $(d_0^2-d^2)s_1$. If the previous consecutive $k - 1$ events are all scoring events, and the $k$-th event before this one is not a scoring event or does not exist, then the player additionally gains $ks_2$.

Settlement in the game happens at times when an integer number of time units has passed since the start of the game. Objects that have already appeared move between two adjacent times, and at the start of a time, movement has already finished. During settlement, all objects are considered stationary. The game starts at time 0. Specifically, for any time moment including time 0: first, this moment starts. Then, all miss events caused by movement happen one by one in some order. Then, objects that appear at this moment appear simultaneously. Then, all operations happen simultaneously, and it is guaranteed that marks made at this moment will not be canceled at the same moment. Then, all scoring events happen one by one in some order (the total score is independent of the order). Then, all miss events caused by operations happen one by one in some order. Then, all objects’ states change simultaneously (disappearing is also considered a state change). Finally, this moment ends.

If all objects have both appeared and disappeared, or the number of miss events becomes strictly greater than $w$, the game ends immediately, and all subsequent operations can be ignored.

Input Format

The first line contains $n,m$, representing the number of objects and the number of operation pairs.

Then follow $n$ lines, each containing $x_i,l_i,r_i,t_i,v_i$.

Then follow $m$ lines, each containing $p_i,a_i,b_i$.

Then one line containing $d_0,s_1,s_2,w$.

Output Format

Output two lines. The first line is the score, and the second line is the game end time.

4 5
4 3 3 7 6
1 8 12 1 2
1 1 3 0 1
2 1 1 0 4
4 6 7
4 7 8
4 8 9
2 0 5
2 5 7
2 5 1 2

62
8

Hint

Sample Explanation

At time 0, two scoring events occurred, and a total of 28 points was obtained. At time 5, one scoring event and one miss event occurred, and 18 points was obtained. At time 7, one scoring event occurred, and 16 points was obtained. At time 8, one miss event occurred. At this point, all objects have appeared and disappeared, and the game ends.

Constraints

All inputs are integers.

$1\le n,m\le 2000$;

$0\le t_i,a_i,b_i\le 10^9$;

$1\le x_i,p_i,l_i,r_i\le 10^9$;

$a_i<b_i$，$l_i\le r_i$；

$1\le v_i,v_i\cdot\max\{t_j,a_j,b_j\}\le 10^9$；

$0\le d_0,s_1,s_2\le 10^4$；

$0\le w\le n$。

For 30% of the testdata: $n,m\le 10$.

Problem Updates

24.11.15: Improved the description of some details in the statement, and added hack testdata.

24.12.24: Added one more set of hack testdata.

Translated by ChatGPT 5