데이트

일리야는 데이트를 좋아한다. 그는 앞으로 $t$일 동안(날짜는 1부터 $t$까지 번호가 매겨져 있다) 데이트를 계획한다. 각 날짜 $x$에 대해 최대 $a_x$번의 데이트를 계획할 수 있다.

일리야에게는 번호가 1부터 $n$까지인 아는 여자가 $n$명 있다. 여자 $i$는 $[l_i, r_i]$ 구간의 어느 날이든 최대 한 번 데이트에 응할 의향이 있으며, 데이트하면 일리야는 $p_i$만큼의 즐거움을 얻는다. 모든 $i < n$에 대해 $l_i \le l_{i+1}$이고 $r_i \le r_{i+1}$이다.

일리야는 여자들 중 일부를 고르고 그 데이트 날짜를 정해서 즐거움의 합을 최대로 만들려고 한다. 얻을 수 있는 즐거움 합의 최댓값을 구하라.

첫 줄에 두 정수 $n$과 $t$가 주어진다($1 \le n, t \le 300000$). 다음 줄에 $t$개의 정수 $a_1, a_2, \ldots, a_t$가 주어진다($0 \le a_i \le n$). 이어지는 $n$개의 줄에는 각각 세 정수 $l_i$, $r_i$, $p_i$가 주어진다($1 \le l_i \le r_i \le t$, $1 \le p_i \le 10^9$).

즐거움 합의 최댓값을 나타내는 정수 하나를 출력하라.