{"raw_statement":[{"iden":"statement","content":"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.\n\nPeking 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.\n\nThe 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 Bi 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.\n\nOn 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 Lj, Rj, and Cj, with the following meaning: the sum of the number of agents hired from the teams from Lj to Rj must be no more than Cj.\n\nNow 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.\n\nThe first line contains two integers, N and M. The second line has N integers, B1, B2, ..., BN, where Bi 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, Lj, Rj, and Cj. Consider that each team appears in at least one of the M constraints.\n\nPrint an integer, the total security score of an optimal hiring plan.\n\n"},{"iden":"input","content":"The first line contains two integers, N and M. The second line has N integers, B1, B2, ..., BN, where Bi 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, Lj, Rj, and Cj. Consider that each team appears in at least one of the M constraints.  1 ≤ N ≤ 200.  1 ≤ M ≤ 4000.  0 ≤ Bi ≤ 2000.  1 ≤ Lj ≤ Rj ≤ N.  0 ≤ Cj ≤ 106. "},{"iden":"output","content":"Print an integer, the total security score of an optimal hiring plan."},{"iden":"examples","content":"Input4 55 12 10 62 4 11 4 13 4 11 1 11 2 1Output12Input2 112 41 2 2Output24"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case, let $ (n, m) \\in \\mathbb{Z}_{\\geq 0}^2 $ denote the sizes of the two rock piles.\n\n**Constraints**  \n1. $ 1 \\leq T \\leq 10^4 $  \n2. $ 0 \\leq n, m \\leq 10^9 $\n\n**Objective**  \nDetermine the winner of a two-player impartial game with state $ (n, m) $, where players alternate turns starting with Hasan. In each turn, a player may:  \n- Remove one rock from the first pile,  \n- Remove one rock from the second pile,  \n- Remove one rock from both piles.  \n\nThe player unable to move loses. Both play optimally.  \n\nOutput \"hasan\" if the first player (Hasan) wins; otherwise output \"abdullah\".  \n\nThe winning condition is determined by the Grundy number or Nim-equivalent of the position. The position $ (n, m) $ is a losing position (P-position) if and only if $ n = m $. Otherwise, it is a winning position (N-position).","simple_statement":"Two piles of rocks, with N and M rocks. Players take turns; Hasan starts. On each turn, a player can take 1 rock from one pile or 1 rock from both piles. The player who cannot move loses. Both play optimally. Print \"hasan\" if Hasan wins, otherwise \"abdullah\".","has_page_source":false}