#P5302. [GXOI/GZOI2019] 特技飞行

[GXOI/GZOI2019] 特技飞行

题目描述

公元 90129012 年,Z 市的航空基地计划举行一场特技飞行表演。表演的场地可以看作一个二维平面直角坐标系,其中横坐标代表着水平位置,纵坐标代表着飞行高度。

在最初的计划中,这 nn 架飞机首先会飞行到起点 x=xstx = x_{st} 处,其中第 ii 架飞机在起点处的高度为 yi,0y_{i,0}。它们的目标是终点 x=xedx = x_{ed} 处,其中第 ii 架飞机在终点处的高度应为 yi,1y_{i,1}。因此,每架飞机可以看作坐标系中的一个点,它的航线是从 (xst,yi,0)(x_{st},y_{i,0}) 出发、到 (xed,yi,1)(x_{ed},y_{i,1}) 结束的一条线段,如下图所示。

aerobatics1.png

nn 架飞机同时出发且始终保持一定的对地速度。因此,对于任意两条交叉的航线(线段),对应的两架飞机必然会同时到达交点处——这就是它们进行特技表演的时刻。它们将会偏转机翼,展现以极近的距离「擦身而过」特技,然后继续保持各自的航线

航空基地最近还研究了一种新的特技「对向交换」。当两架飞机到达交点处时,之前正在下降的那架立即转为执行抬升动作,之前正在上升的那架则执行一次空翻,两架飞机一上一下、机腹对机腹,同样以极近的距离经过交点,然后互相交换接下来的航线

我们不必关心特技动作在物理上究竟是如何实现的,飞机仍然看作一个点,在两种特技动作下,航线的变化如下图所示(yi,1y_{i,1}' 表示交换航线后第 ii 架飞机在终点的新高度)。容易发现,「对向交换」会使它们的航线变为折线,并保持它们在纵坐标上的相对顺序;而「擦身而过」会改变它们在纵坐标上的相对顺序

aerobatics2.png

现在,观看表演的嘉宾团提出了一个苛刻的要求——在终点 x=xedx = x_{ed} 处,按照高度排序,nn 架飞机的相对顺序必须与 x=xstx = x_{st} 处的相对顺序一致。嘉宾团还给「对向交换」特技和「擦身而过」特技分别评定了难度系数 aabb,每次「对向交换」特技可以获得 aa 的分数,每次「擦身而过」特技可以获得 bb 的分数。

除此以外,嘉宾团共有 kk 名成员,第 ii 名成员会乘热气球停留在位置 (pi,qi)(p_i,q_i) 处,具有 rir_i 的观测距离,可以观测到区域 xpi+ypiri|x - p_i| + |y - p_i| \le r_i 里的所有特技。
若某个交点处的特技被一名或多名嘉宾观测到,则可以获得 cc 的额外加分。
注意:特技无论是否被观测到,均可以获得 aa 或者 bb 的得分

下图是对本题第一幅图 44 条航线 44 个交点的一种满足要求的安排,包括 22 次「对向交换」、22 次「擦身而过」,33 项特技被观测到,得分 2a+2b+3c2a + 2b + 3c。为了方便观察,图中展现「对向交换」特技的交点稍稍有些分离。

aerobatics3.png

在这次的剧情里,你成为了 Z 市航空基地的规划员,你可以决定在每个交点处是执行「对向交换」还是「擦身而过」。你被要求在保证嘉宾团要求的前提下,计算整个特技表演的可能得到的最低和最高分数。

输入格式

第一行包含六个非负整数 n,a,b,c,xst,xedn,a,b,c,x_{st},x_{ed},分别表示航线(线段)总数、「对向交换」特技的得分、「擦身而过」特技的得分、观测对表演的额外分、飞行起点的横坐标、飞行终点的横坐标。

第二行包含 nn 个非负整数 yi,0y_{i,0},其中第 ii 个数表示第 ii 条航线起点的纵坐标,保证按照从低到高的顺序给出,即 yi,0<yi+1,0y_{i,0} < y_{i + 1,0}

第三行包含 nn 个非负整数 yi,1y_{i,1},其中第 ii 个数表示第 ii 条航线终点的纵坐标。

第四行包含一个非负整数 kk,表示嘉宾的数量。

接下来 kk 行每行三个非负整数 pi,qi,rip_i,q_i,r_i,分别表示第 ii 名嘉宾所在位置的横、纵坐标与观测距离。

输入数据对于所有航线(线段)在直线 x=xstx = x_{st}x=xedx = x_{ed} 之间的交点总数也有一些限制,详见「数据范围与提示」。

输出格式

输出只有一行,包含两个整数,表示整个特技飞行表演的可能得到的最低和最高分数,中间用一个空格隔开。

4 1 2 3 1 6
1 2 3 4
4 1 3 2
2
3 3 1
5 2 2
13 15
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
989 1619

提示

样例1解释

该样例的航线就是题目描述的图中所画的情况,只是嘉宾所在的位置稍有不同。
最低得分的表演方案是在所有交点处均采用「对向交换」特技,得分 4a+3c=134a + 3c = 13
最高得分的表演方案与题目描述的图中所画的情况一致,得分 2a+2b+3c=152a + 2b + 3c = 15

数据范围

不存在三条或三条以上的线段交于同一点。
所有坐标和 rir_i 均为 5×1075 \times 10^7 以内的非负整数。
yi,0<yi+1,0y_{i,0} < y_{i + 1,0}yi,1y_{i,1} 各不相同。
xst<pi<xed,1a,b,c103x_{st} < p_i < x_{ed},1 ≤ a,b,c ≤ 10^3

测试点编号 n,kn,k 的规模 交点数的规模 约定
11 n,k15n,k \le 15 40\le 40
22
33
44
55 n30.000,k100n \le 30.000,k \le 100 200,000\le 200,000
66
77
88
99 n,k100,000n,k \le 100,000 500,000\le 500,000 a=ba = b
1010
1111
1212
1313 n,k50,000n,k \le 50,000 250,000\le 250,000
1414
1515
1616
1717 n,k100,000n,k \le 100,000 500,000\le 500,000
1818
1919
2020