题目描述

考虑这样一款游戏，游戏地图可以视为一个平面直角坐标系的第一、四象限。

第一象限内会出现 $n$ 个物体，一个物体可以是一个点，或者一条平行于 y 轴的线段。一个物体出现时，物体上离 x 轴最近的点和最远的点，分别称为物体的最低点和最高点。若物体是点，则最低点和最高点相同。

第 $i$ 个物体会在时刻 $t_i$ 出现，最低点为 $(x_i,l_i)$，最高点为 $(x_i,r_i)$，以速度 $v_i$ 沿 y 轴负半轴方向匀速移动。

玩家可以标记 x 轴正半轴上的任何整点（若这个位置已经被标记，则这次的标记和之前的标记互不影响），称为标记操作；也可以取消某个标记，称为取消标记操作。同一时间可以做任意次操作。已知玩家做了 $m$ 对操作，第 $i$ 对操作的位置为 $p_i$，其中标记操作和取消标记操作发生的时刻分别为 $a_i$ 和 $b_i$。

每个物体最初会处于正常状态。

若在某一时刻，对于一个物体，距离物体的最低点不大于 $d_0$ 的位置发生标记操作，且这个物体处于正常状态，则会发生得分事件，且事件的参数 $d$ 为操作位置与物体最低点的距离。若有多个标记操作符合条件，选择其中使得 $d$ 最小的，若仍有多个则选择其中位置最接近原点的，保证这样选出的操作是唯一的。随后，对于这个物体，若是一个点，则会消失，否则会被这个操作标记，且变成被标记状态。注意，一个操作可以影响多个物体，而一个物体不会被多个操作标记。

若在某一时刻，对于一个物体，距离物体的最高点不大于 $d_0$ 位置发生取消标记操作，且这个物体被相应的标记操作标记，则也会发生得分事件，且事件的参数 $d$ 为操作位置与物体最高点的距离。随后，这个物体会消失。

若在某一时刻，一个处于正常状态的物体的最低点到达了第四象限（注意，坐标轴上的点不属于任何一个象限），或一个处于被标记状态的物体对应的标记被取消，且没有因为取消标记发生得分事件，则会发生 miss 事件。随后，这个物体会消失。

一个参数为 $d$ 的得分事件发生时，玩家会得到 $(d_0^2-d^2)s_1$ 的基本得分。若此次事件前的连续 $k - 1$ 次事件都是得分事件，且此次事件前的第 $k$ 次事件不是得分事件或不存在，则玩家会得到 $ks_2$ 的额外得分。

游戏中的结算发生在距离游戏开始经过整数个单位时间的时刻之内。已经出现的物体会在相邻两个时刻之间进行移动，某一时刻开始时移动已经完成。在结算的过程中，所有物体均视为静止。游戏开始于 0 时刻。具体来说，对于包括 0 时刻在内的任一时刻：首先，这一时刻开始。随后，所有由移动造成的 miss 事件以某个顺序依次发生。随后，在这一时刻出现的物体同时出现。随后，所有操作同时发生，且保证这一时刻的标记不会在同一时刻被取消。随后，所有得分事件以某个顺序依次发生（总得分与顺序无关）。随后，所有由操作造成的 miss 事件以某个顺序依次发生。随后，所有物体的状态同时改变（消失也视为状态改变）。最后，这一时刻结束。

若所有物体均经历了出现和消失，或 miss 事件发生了严格大于 $w$ 次，游戏立即结束，此后的操作均可以忽略。

输入格式

第一行 $n,m$，分别表示物体的个数和操作的对数。

之后 $n$ 行，每行 $x_i,l_i,r_i,t_i,v_i$。

之后 $m$ 行，每行 $p_i,a_i,b_i$。

之后一行，$d_0,s_1,s_2,w$。

输出格式

输出两行，第一行为得分，第二行为游戏结束时刻。

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

提示

样例说明

在时刻 0 发生了两次得分事件，共得到了 28 分；在时刻 5 发生了一次得分事件和一次 miss 事件，得到了 18 分；在时刻 7 发生了一次得分事件，得到了 16 分；在时刻 8 发生了一次 miss 事件，至此，所有物体都经历了出现和消失，游戏结束。

数据范围

所有输入均为整数。

$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$。

对于30%的数据：$n,m\le 10$。

题目更新

24.11.15：对于题意的细节改进了描述方式，增加了 hack 数据。