18450번 - Dates 다국어

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 ax 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 pi pleasure for dating this girl. For each i < n, it is true that l_i ≤ l_i+1 and r_i ≤ 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.

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

The next line contains t integers a₁, a₂, . . . , a_t: here, a_i is the maximum number of dates Ilya can plan on day i (0 ≤ ai ≤ 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 ≤ l_i ≤ r_i ≤ t, 1 ≤ p_i ≤ 10⁹).

It is guaranteed that, for each i < n, it is true that l_i ≤ l_i+1 and r_i ≤ r_i+1.

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