{"raw_statement":[{"iden":"problem statement","content":"You are given an integer sequence $A=(A_1,A_2,\\dots,A_N)$ of length $N$.\nFind the maximum value of $\\displaystyle \\sum_{i=1}^{M} i \\times B_i$ for a contiguous subarray $B=(B_1,B_2,\\dots,B_M)$ of $A$ of length $M$."},{"iden":"notes","content":"A **contiguous subarray** of a number sequence is a sequence that is obtained by removing $0$ or more initial terms and $0$ or more final terms from the original number sequence.\nFor example, $(2, 3)$ and $(1, 2, 3)$ are contiguous subarrays of $(1, 2, 3, 4)$, but $(1, 3)$ and $(3,2,1)$ are not contiguous subarrays of $(1, 2, 3, 4)$."},{"iden":"constraints","content":"*   $1 \\le M \\le N \\le 2 \\times 10^5$\n*   $- 2 \\times 10^5 \\le A_i \\le 2 \\times 10^5$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $A_2$ $\\dots$ $A_N$"},{"iden":"sample input 1","content":"4 2\n5 4 -1 8"},{"iden":"sample output 1","content":"15\n\nWhen $B=(A_3,A_4)$, we have $\\displaystyle \\sum_{i=1}^{M} i \\times B_i = 1 \\times (-1) + 2 \\times 8 = 15$. Since it is impossible to achieve $16$ or a larger value, the solution is $15$.\nNote that you are not allowed to choose, for instance, $B=(A_1,A_4)$."},{"iden":"sample input 2","content":"10 4\n-3 1 -4 1 -5 9 -2 6 -5 3"},{"iden":"sample output 2","content":"31"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}