{"raw_statement":[{"iden":"statement","content":"Little Alyona is celebrating Happy Birthday! Her mother has an array of _n_ flowers. Each flower has some mood, the mood of _i_\\-th flower is _a__i_. The mood can be positive, zero or negative.\n\nLet's define a subarray as a segment of consecutive flowers. The mother suggested some set of subarrays. Alyona wants to choose several of the subarrays suggested by her mother. After that, each of the flowers will add to the girl's happiness its mood multiplied by the number of chosen subarrays the flower is in.\n\nFor example, consider the case when the mother has 5 flowers, and their moods are equal to 1,  - 2, 1, 3,  - 4. Suppose the mother suggested subarrays (1,  - 2), (3,  - 4), (1, 3), (1,  - 2, 1, 3). Then if the girl chooses the third and the fourth subarrays then:\n\n*   the first flower adds 1·1 = 1 to the girl's happiness, because he is in one of chosen subarrays,\n*   the second flower adds ( - 2)·1 =  - 2, because he is in one of chosen subarrays,\n*   the third flower adds 1·2 = 2, because he is in two of chosen subarrays,\n*   the fourth flower adds 3·2 = 6, because he is in two of chosen subarrays,\n*   the fifth flower adds ( - 4)·0 = 0, because he is in no chosen subarrays.\n\nThus, in total 1 + ( - 2) + 2 + 6 + 0 = 7 is added to the girl's happiness. Alyona wants to choose such subarrays from those suggested by the mother that the value added to her happiness would be as large as possible. Help her do this!\n\nAlyona can choose any number of the subarrays, even 0 or all suggested by her mother."},{"iden":"input","content":"The first line contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 100) — the number of flowers and the number of subarrays suggested by the mother.\n\nThe second line contains the flowers moods — _n_ integers _a_1, _a_2, ..., _a__n_ ( - 100 ≤ _a__i_ ≤ 100).\n\nThe next _m_ lines contain the description of the subarrays suggested by the mother. The _i_\\-th of these lines contain two integers _l__i_ and _r__i_ (1 ≤ _l__i_ ≤ _r__i_ ≤ _n_) denoting the subarray _a_\\[_l__i_\\], _a_\\[_l__i_ + 1\\], ..., _a_\\[_r__i_\\].\n\nEach subarray can encounter more than once."},{"iden":"output","content":"Print single integer — the maximum possible value added to the Alyona's happiness."},{"iden":"examples","content":"Input\n\n5 4\n1 -2 1 3 -4\n1 2\n4 5\n3 4\n1 4\n\nOutput\n\n7\n\nInput\n\n4 3\n1 2 3 4\n1 3\n2 4\n1 1\n\nOutput\n\n16\n\nInput\n\n2 2\n-1 -2\n1 1\n1 2\n\nOutput\n\n0"},{"iden":"note","content":"The first example is the situation described in the statements.\n\nIn the second example Alyona should choose all subarrays.\n\nThe third example has answer 0 because Alyona can choose none of the subarrays."}],"translated_statement":[{"iden":"statement","content":"小Alyona正在庆祝生日！她的妈妈有一排 #cf_span[n] 朵花。每朵花都有一定的情绪，第 #cf_span[i] 朵花的情绪为 #cf_span[ai]。情绪可以是正数、零或负数。\n\n我们定义一个子数组为一段连续的花。妈妈提出了一些子数组。Alyona希望从妈妈提出的子数组中选择若干个。之后，每朵花会为其幸福感贡献其情绪乘以包含它的被选子数组的数量。\n\n例如，考虑妈妈有 #cf_span[5] 朵花，其情绪为 #cf_span[1,  - 2, 1, 3,  - 4] 的情况。假设妈妈提出的子数组为 #cf_span[(1,  - 2)]、#cf_span[(3,  - 4)]、#cf_span[(1, 3)]、#cf_span[(1,  - 2, 1, 3)]。如果女孩选择了第三和第四个子数组，则：\n\n因此，总共 #cf_span[1 + ( - 2) + 2 + 6 + 0 = 7] 被加到女孩的幸福感中。Alyona希望从妈妈提出的子数组中选择若干个，使得加到她幸福感的值尽可能大。请帮助她实现这一点！\n\nAlyona可以选择任意数量的子数组，包括 #cf_span[0] 个或全部妈妈提出的子数组。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n, m ≤ 100]) —— 花的数量和妈妈提出的子数组数量。\n\n第二行包含花的情绪 —— #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[ - 100 ≤ ai ≤ 100])。\n\n接下来的 #cf_span[m] 行描述了妈妈提出的子数组。第 #cf_span[i] 行包含两个整数 #cf_span[li] 和 #cf_span[ri] (#cf_span[1 ≤ li ≤ ri ≤ n])，表示子数组 #cf_span[a[li], a[li + 1], ..., a[ri]]。\n\n每个子数组可能出现多次。\n\n输出一个整数 —— 加到Alyona幸福感的最大可能值。"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n, m ≤ 100]) —— 花的数量和妈妈提出的子数组数量。第二行包含花的情绪 —— #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[ - 100 ≤ ai ≤ 100])。接下来的 #cf_span[m] 行描述了妈妈提出的子数组。第 #cf_span[i] 行包含两个整数 #cf_span[li] 和 #cf_span[ri] (#cf_span[1 ≤ li ≤ ri ≤ n])，表示子数组 #cf_span[a[li], a[li + 1], ..., a[ri]]。每个子数组可能出现多次。"},{"iden":"output","content":"输出一个整数 —— 加到Alyona幸福感的最大可能值。"},{"iden":"examples","content":"输入\n5 4\n1 -2 1 3 -4\n1 2\n4 5\n3 4\n1 4\n输出\n7\n\n输入\n4 3\n1 2 3 4\n1 3\n2 4\n1 1\n输出\n16\n\n输入\n2 2\n-1 -2\n1 1\n1 2\n输出\n0"},{"iden":"note","content":"第一个例子是题面中描述的情形。在第二个例子中，Alyona应选择所有子数组。第三个例子的答案为 #cf_span[0]，因为Alyona可以选择不选任何子数组。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ be the number of flowers and suggested subarrays, respectively.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the sequence of flower moods, where $ a_i \\in \\mathbb{Z} $ and $ -100 \\leq a_i \\leq 100 $.  \nLet $ \\mathcal{S} = \\{ (l_j, r_j) \\mid j \\in \\{1, \\dots, m\\} \\} $ be the multiset of suggested subarrays, where each $ (l_j, r_j) $ denotes the subarray $ [a_{l_j}, a_{l_j+1}, \\dots, a_{r_j}] $.\n\nLet $ x_j \\in \\{0, 1\\} $ be a binary variable indicating whether subarray $ j $ is chosen ($ x_j = 1 $) or not ($ x_j = 0 $).\n\nFor each flower $ i \\in \\{1, \\dots, n\\} $, define $ c_i = \\sum_{j=1}^m x_j \\cdot \\mathbf{1}_{[l_j \\leq i \\leq r_j]} $, the number of chosen subarrays containing flower $ i $.\n\n**Constraints**  \n1. $ 1 \\leq n, m \\leq 100 $  \n2. $ -100 \\leq a_i \\leq 100 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ 1 \\leq l_j \\leq r_j \\leq n $ for all $ j \\in \\{1, \\dots, m\\} $  \n4. $ x_j \\in \\{0, 1\\} $ for all $ j \\in \\{1, \\dots, m\\} $\n\n**Objective**  \nMaximize the total happiness:  \n$$\n\\max_{x_1, \\dots, x_m \\in \\{0,1\\}} \\sum_{i=1}^n a_i \\cdot c_i = \\max_{x_1, \\dots, x_m \\in \\{0,1\\}} \\sum_{i=1}^n a_i \\left( \\sum_{j=1}^m x_j \\cdot \\mathbf{1}_{[l_j \\leq i \\leq r_j]} \\right)\n$$  \nEquivalently:  \n$$\n\\max_{x_1, \\dots, x_m \\in \\{0,1\\}} \\sum_{j=1}^m x_j \\left( \\sum_{i=l_j}^{r_j} a_i \\right)\n$$","simple_statement":null,"has_page_source":false}