题目描述

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

第一象限内会出现$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$次得分事件，且没有连续发生$k+1$次得分事件，则玩家会得到$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$。