Zulu is an adventurous kid. He loves to visit new places and play adventure games. Once he visited Wonderla, a park famous for its adventurous games. Unfortunately he got stuck in one of the games he was playing.

This game has N levels. Each of the level contain some valuable types of items. There are in total M types of items. Each type of item has three integers associated with it. Firstly, it has Value which corresponds to the profit made when 1 unit of this item is picked. Second integer contains Time which corresponds to the time needed for picking this item. Third and last integer denote the Level which corresponds to the level number in which this item is present. Also, the expiry time of each level is given as well, i.e., the time when this level gets disappeared and is denoted by $E[i]$ for the $i^{th}$ level. Now there are some rules in the game which needs to be followed:

• It is not allowed to pick any item from a particular level if the current time $+$ time to pick that item exceeds the expiry time of that level.

• It is not allowed to pick an item from the higher levels if at least one of the lower levels have been expired.

Note that each level has infinite supply for each type of items which are present at that level. Now, the task of Zulu is to collect as much profit as possible and predict the highest possible profit so that he can win the game. Can you help him achieve this task?

Input:

First line contain two integers N and M which denote number of levels and total number of items respectively.

Second line contains N integers which denote the expiry time of the levels.

Lastly, there are M lines where there are three space-separated integers present in each of the line. First integer denote Value, second contain Time and third contains Level.

Output:

In a single line output the maximum possible profit that can made by Zulu.

Constraints:

$1 \le N, M \le 2000$

$1 \le Value \le 10^9$

$1 \le Time, E[i] \le 2000$

$1 \le Level \le N$