드론

농부가 한 직선 위에 놓인 희귀한 꽃을 키운다. 꽃은 모두 $n$송이이고, 각 꽃 $f\_i$는 직선 위의 위치 $x\_i$에 있다. 각 꽃은 직선 위의 점으로 볼 수 있다. 농부는 꽃에 정기적으로 비료를 주려고 비료 드론 여러 대를 빌린다.

드론은 비행하면서 땅에 비료를 뿌린다. 각 드론의 비행 경로는 선분이며, 닫힌 구간으로 볼 수 있다. 주어진 드론은 $m$대이고, 드론 $D\_i$의 구간은 $[a\_i, b\_i]$, 비용은 $c\_i$이다. 주어진 모든 점이 선택한 구간 중 적어도 하나에 포함되도록 드론 집합을 골라야 한다. 즉, 선택한 구간들의 합집합이 모든 점을 포함해야 한다. 이 조건을 만족하는 드론 집합을 후보 집합이라고 한다.

모든 점과 모든 구간의 끝점은 서로 다른 좌표를 가진다고 가정한다. 점이 구간에 포함되면 그 구간이 점을 덮는다고 한다. 후보 집합 $X$에서 각 점이 치르는 비용은 $X$의 구간 중 그 점을 덮는 구간들의 비용 합이다. 모든 후보 집합에 대해 점 비용의 최댓값을 구하고, 그 최댓값이 가장 작아지는 값을 찾아라.

예를 들어 그림에는 점 다섯 개와 구간 네 개가 있다. 각 구간 위의 숫자는 비용이다. 후보 집합은 세 가지이며, $\{[1, 5], [6, 10], [8, 13]\}$, $\{[1, 5], [3, 11], [8, 13]\}$, 그리고 구간 네 개를 모두 고른 집합이다. 첫 번째 집합에서는 위치 9의 점이 비용 4를 치른다. 두 번째와 세 번째 집합에서는 같은 점이 각각 3과 5를 치른다. 따라서 점 비용 최댓값의 최솟값은 3이다.

첫 줄에 두 정수 $n$과 $m$이 주어진다 ($n \ge 1$, $2 \le n + m \le 100,000$, $1 \le m \le 2,000$). $n$은 점의 개수이고 $m$은 구간의 개수이다. 둘째 줄에는 점의 위치 $n$개가 주어지며, 각 값은 0 이상 $10^9$ 이하이다. 이어지는 $m$개의 줄에는 세 정수 $a$, $b$, $c$가 한 줄씩 주어진다. 이는 구간 $[a, b]$와 비용 $c$를 뜻한다 ($0 \le a < b \le 10^9$, $1 \le c \le 10^9$). 모든 점과 모든 구간의 끝점은 서로 다른 좌표를 가진다.

모든 후보 집합 중 점 비용 최댓값의 최솟값을 한 줄에 출력한다. 후보 집합이 없으면 -1을 출력한다.