404392: GYM101492 I Protecting the Great Wall

China has a very rich history, with written records since 1,500BC. One of the cities that contributes a lot to this history is the capital city of Peking. It is visited yearly by many tourists seeking to get to places such as the Temple of Heaven, the Lugou Bridge, the Yinshan Pagoda Forest, or the Forbidden City. One of the most imposing tourist attractions is the Great Wall, for its history and sheer size.

Peking will host the ACM ICPC World Finals 2018, and one of the chosen group activities is to visit the Great Wall. The event organizers in China want to make these one of the best World Finals ever. They have been planning activities with great care for the safety of all participants throughout the city. For this reason, they charged Marcel "the optimizer" Saito with the job of securing the visit to the Great Wall.

The organizers can hire agents from N security teams, numbered from 1 to N. They may hire any number of agents (possibly none) from each team. The organizers assigned each of these teams a security value, that is, each agent in the i-th team adds B_i points to the security score. Marcel's goal is to come up with a hiring plan for agents so as to maximize the total security score, which is the sum of the security values of the hired agents.

On the other hand, the organizers informed Marcel that each group has its special workflow which may cause conflicts. For this reason, the hiring plan must satisfy a set of M constraints. The j-th constraint is defined by three integers L_j, R_j, and C_j, with the following meaning: the sum of the number of agents hired from the teams from L_j to R_j must be no more than C_j.

Now Marcel has all the data to find an optimal hiring plan and keep his reputable epithet. This looks like an interesting problem, so we want you to solve it as well.

The first line contains two integers, N and M. The second line has N integers, B₁, B₂, ..., B_N, where B_i is the security value of the agents in the i-th group. The next M lines contain information about each one of the constraints. The j-th of these M lines contains three integers, L_j, R_j, and C_j. Consider that each team appears in at least one of the M constraints.

• 1 ≤ N ≤ 200.
• 1 ≤ M ≤ 4000.
• 0 ≤ B_i ≤ 2000.
• 1 ≤ L_j ≤ R_j ≤ N.
• 0 ≤ C_j ≤ 10⁶.

Print an integer, the total security score of an optimal hiring plan.

4 5
5 12 10 6
2 4 1
1 4 1
3 4 1
1 1 1
1 2 1

12

2 1
12 4
1 2 2

24