#P18721. Tsunami

    ID: 18057 传统题 5000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF2900省选/NOI-线性 DP有限候选集缩减绝对值分段线性化Li Chao 线段树懒标记线段树同时事件分阶段处理

Tsunami

Tsunami

全球变暖和环境危机使我们不得不为可能出现的自然灾害准备生存方案。这次要制定一份海啸疏散手册。

把城市地图表示为二维坐标平面。海岸线是一条平行于横轴的直线 y=ky=k。通常 k=0k=0,发生海啸后它变为一个正整数。

城市中有 nn 个互不相同的疏散集合点 (pi,qi)(p_i,q_i)。你已知独自到达第 ii 个集合点需要 rir_i 分钟。疏散手册有两步:

  1. 选择一个集合点 (pi,qi)(p_i,q_i),独自花费 rir_i 分钟到达那里。
  2. 在那里与大家集合,再按下述规则一起前往安全线 y=ky=k。

疏散途中有障碍。每个障碍是平行于横轴的闭线段,用 (si,ei,yi,ti)(s_i,e_i,y_i,t_i) 表示,从 (si,yi)(s_i,y_i) 延伸到 (ei,yi)(e_i,y_i),跨越它需要 tit_i 分钟。**即使从端点跨越,也要花费 tit_i 分钟。**没有集合点落在任何障碍上。

障碍之间可以重叠,跨越重叠部分的耗时为各个障碍耗时之和。例如两个障碍为 (1,4,2,5)(1,4,2,5) 和 (3,5,2,7)(3,5,2,7),在横坐标 11 跨越耗时 55,在横坐标 33 跨越耗时 5+7=125+7=12,在横坐标 55 跨越耗时 77。同一高度的全部障碍在该高度一并跨越,不能在跨越它们之间于该整数高度横移。

纵坐标只能增加,直到到达安全线。上升过程中可以改变横坐标。当当前位置的纵坐标严格介于整数 ii 与 i+1i+1 之间时,横坐标每向任一方向变化 11,耗时 cic_i 分钟。例如 c3=5c_3=5 时,在高度 y=3.5y=3.5 从横坐标 1010 移到 66,耗时 5∣10−6∣=205|10-6|=20 分钟。竖直上升的耗时忽略不计,只计算横向移动耗时。

横坐标只能取整数,并且不能在整数纵坐标处横移。除此以外没有限制:例如可以去横坐标 −100-100 或 1010010^{100},不要求一直待在 11 到 xx 之间。

c1,c2,…,ck−1c_1,c_2,\ldots,c_{k-1} 非递减:高度越高,人越多,横向穿行越困难。

请分别求到达 (1,k),(2,k),…,(x,k)(1,k),(2,k),\ldots,(x,k) 的最少总耗时(包括第一步的 rir_i)。不同目标可以选择不同的集合点和路线。

输入格式

第一行两个整数 x,kx,k,3≤x,k≤2⋅1053\le x,k\le2\cdot10^5。

第二行两个整数 n,mn,m,1≤n≤2⋅1051\le n\le2\cdot10^5,0≤m≤2⋅1050\le m\le2\cdot10^5。

接下来 nn 行,每行三个整数 pi,qi,rip_i,q_i,r_i,表示集合点和自行前往的耗时:

$$1\le p_i\le x,\quad1\le q_i<k,\quad0\le r_i\le10^{15}.$$

所有点 (pi,qi)(p_i,q_i) 互不相同;仅横坐标相同的点是允许的。

接下来 mm 行,每行四个整数 si,ei,yi,tis_i,e_i,y_i,t_i,表示一个障碍:

$$1\le s_i\le e_i\le x,\quad2\le y_i<k,\quad0\le t_i\le10^9.$$

障碍可有公共点,但没有任何集合点落在障碍上,耗时为 00 的障碍也不例外。

最后一行 k−1k-1 个整数:

0≤c1≤c2≤⋯≤ck−1≤106.0\le c_1\le c_2\le\cdots\le c_{k-1}\le10^6.

cic_i 对应的是纵坐标严格介于 ii 和 i+1i+1 之间的横向单位移动耗时。

输出格式

输出 xx 行,第 ii 行一个整数,表示到达 (i,k)(i,k) 的最少分钟数。

原样例

10 10
3 5
9 3 5
5 2 34
2 1 43
6 10 2 19
7 9 2 86
2 10 4 87
2 3 2 17
2 2 2 49
1 1 1 2 7 7 8 10 10
13
15
17
19
19
17
15
13
11
9