题目描述

图中有 $n$ 栋建筑，编号为 $0$ 到 $n-1$；还有 $m$ 座天桥，编号为 $0$ 到 $m-1$。

这张规划图绘制在二维平面上，其中建筑和天桥分别表示为垂直线段和水平线段。

第 $i$ 栋建筑（$0\le i\le n-1$）的底部位于坐标 $(x[i],0)$，建筑高度为 $h[i]$。因此，它对应一条连接

和

的垂直线段。

第 $j$ 座天桥（$0\le j\le m-1$）的两端分别位于第 $l[j]$ 栋建筑和第 $r[j]$ 栋建筑上，其纵坐标为正整数 $y[j]$。因此，它对应一条连接

和

的水平线段。

如果某座天桥和某栋建筑存在公共点，则称它们相交。因此，一座天桥一定会在两个端点处与对应的两栋建筑相交，也可能在中间与其他建筑相交。

你需要求出从第 $s$ 栋建筑的底部到第 $t$ 栋建筑的底部的最短路径长度，或者判断这样的路径不存在。

行人只能沿着建筑和天桥行走，不能在地面上行走，即不能沿纵坐标为 $0$ 的水平线行走。

行人可以在任意交点处从天桥走入建筑，或从建筑走上天桥。如果两座天桥的端点之一位于同一个点，行人也可以直接从其中一座天桥走到另一座天桥。

输入格式

第一行包含两个整数 $n,m$，分别表示建筑数量和天桥数量。

接下来 $n$ 行，第 $i$ 行包含两个整数 $x[i],h[i]$，表示第 $i$ 栋建筑的横坐标和高度。

接下来 $m$ 行，第 $j$ 行包含三个整数 $l[j],r[j],y[j]$，表示第 $j$ 座天桥的左右端点所在建筑编号及其纵坐标。

最后一行包含两个整数 $s,t$，表示起点建筑和终点建筑。

输出格式

如果从第 $s$ 栋建筑的底部到第 $t$ 栋建筑的底部存在可行路径，输出最短路径的长度；否则输出 -1。

样例输入

7 7
0 8
3 7
5 9
7 7
10 6
12 6
14 9
0 1 1
0 2 6
0 6 8
2 3 1
2 6 7
3 4 2
4 6 5
1 5

样例输出

27

样例解释

下图中的蓝色折线给出了一条从第 $1$ 栋建筑底部到第 $5$ 栋建筑底部的最短路径，其长度为 $27$。

数据范围

对于所有测试数据：

除在端点处外，任意两座天桥不会有其他公共点。

子任务