D. Dates
time limit per test
2 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

Ilya loves dating! He is planning his dates for the next $$$t$$$ days (these days are numbered from $$$1$$$ to $$$t$$$). For each day $$$x$$$, he knows that he can plan at most $$$a_x$$$ dates.

Ilya has $$$n$$$ known girls numbered from $$$1$$$ to $$$n$$$. Girl $$$i$$$ is willing to go on a date with him at most once, on any day in $$$[l_i, r_i]$$$, and Ilya will get $$$p_i$$$ pleasure for dating this girl. For each $$$i < n$$$, it is true that $$$l_i \leq l_{i+1}$$$ and $$$r_i \leq r_{i+1}$$$.

Ilya's goal is to plan dates with some girls to maximize total pleasure. Help him! Find the maximum total pleasure he can get if he will properly choose the girls and the days of dates with them.

Input

The first line contains two integers $$$n$$$ and $$$t$$$: the number of girls and the number of days ($$$1 \leq n, t \leq 300\,000$$$).

The next line contains $$$t$$$ integers $$$a_1, a_2, \ldots, a_t$$$: here, $$$a_i$$$ is the maximum number of dates Ilya can plan on day $$$i$$$ ($$$0 \leq a_i \leq n$$$).

The next $$$n$$$ lines contain the descriptions of the girls. The $$$i$$$-th of these lines contains three integers, $$$l_i$$$, $$$r_i$$$, and $$$p_i$$$: the borders of the $$$i$$$-th girl's days segment and the pleasure Ilya will get for dating her ($$$1 \leq l_i \leq r_i \leq t$$$, $$$1 \leq p_i \leq 10^9$$$).

It is guaranteed that, for each $$$i < n$$$, it is true that $$$l_i \leq l_{i+1}$$$ and $$$r_i \leq r_{i+1}$$$.

Output

Print one integer: the maximum total pleasure Ilya can get if he will properly choose the girls and the days of dates with them.

Example
Input
3 5
0 1 0 1 0
1 2 2
2 4 1
3 5 5
Output
7