#P18721. Tsunami
Tsunami
Tsunami
全球变暖和环境危机使我们不得不为可能出现的自然灾害准备生存方案。这次要制定一份海啸疏散手册。
把城市地图表示为二维坐标平面。海岸线是一条平行于横轴的直线 。通常 ,发生海啸后它变为一个正整数。
城市中有 个互不相同的疏散集合点 。你已知独自到达第 个集合点需要 分钟。疏散手册有两步:
- 选择一个集合点 ,独自花费 分钟到达那里。
- 在那里与大家集合,再按下述规则一起前往安全线 。
疏散途中有障碍。每个障碍是平行于横轴的闭线段,用 表示,从 延伸到 ,跨越它需要 分钟。**即使从端点跨越,也要花费 分钟。**没有集合点落在任何障碍上。
障碍之间可以重叠,跨越重叠部分的耗时为各个障碍耗时之和。例如两个障碍为 和 ,在横坐标 跨越耗时 ,在横坐标 跨越耗时 ,在横坐标 跨越耗时 。同一高度的全部障碍在该高度一并跨越,不能在跨越它们之间于该整数高度横移。
纵坐标只能增加,直到到达安全线。上升过程中可以改变横坐标。当当前位置的纵坐标严格介于整数 与 之间时,横坐标每向任一方向变化 ,耗时 分钟。例如 时,在高度 从横坐标 移到 ,耗时 分钟。竖直上升的耗时忽略不计,只计算横向移动耗时。
横坐标只能取整数,并且不能在整数纵坐标处横移。除此以外没有限制:例如可以去横坐标 或 ,不要求一直待在 到 之间。
非递减:高度越高,人越多,横向穿行越困难。
请分别求到达 的最少总耗时(包括第一步的 )。不同目标可以选择不同的集合点和路线。
输入格式
第一行两个整数 ,。
第二行两个整数 ,,。
接下来 行,每行三个整数 ,表示集合点和自行前往的耗时:
$$1\le p_i\le x,\quad1\le q_i<k,\quad0\le r_i\le10^{15}.$$所有点 互不相同;仅横坐标相同的点是允许的。
接下来 行,每行四个整数 ,表示一个障碍:
$$1\le s_i\le e_i\le x,\quad2\le y_i<k,\quad0\le t_i\le10^9.$$障碍可有公共点,但没有任何集合点落在障碍上,耗时为 的障碍也不例外。
最后一行 个整数:
对应的是纵坐标严格介于 和 之间的横向单位移动耗时。
输出格式
输出 行,第 行一个整数,表示到达 的最少分钟数。
原样例
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