{"problem":{"name":"Index × A(Not Continuous ver.)","description":{"content":"You are given an integer sequence $A=(A_1,A_2,\\dots,A_N)$ of length $N$. Find the maximum value of $\\displaystyle \\sum_{i=1}^{M} i \\times B_i$ for a (not necessarily contiguous) subsequence $B=(B_1,B_","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc267_d"},"statements":[{"statement_type":"Markdown","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 (not necessarily contiguous) subsequence $B=(B_1,B_2,\\dots,B_M)$ of length $M$ of $A$.\n\n## Constraints\n\n*   $1 \\le M \\le N \\le 2000$\n*   $- 2 \\times 10^5 \\le A_i \\le 2 \\times 10^5$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $A_2$ $\\dots$ $A_N$\n\n[samples]\n\n## Notes\n\nA **subsequence** of a number sequence is a sequence that is obtained by removing $0$ or more elements from the original number sequence and concatenating the remaining elements without changing the order.\nFor example, $(10,30)$ is a subsequence of $(10,20,30)$, but $(20,10)$ is not a subsequence of $(10,20,30)$.","is_translate":false,"language":"English"}],"meta":{"iden":"abc267_d","tags":[],"sample_group":[["4 2\n5 4 -1 8","21\n\nWhen $B=(A_1,A_4)$, we have $\\displaystyle \\sum_{i=1}^{M} i \\times B_i = 1 \\times 5 + 2 \\times 8 = 21$. Since it is impossible to achieve $22$ or a larger value, the solution is $21$."],["10 4\n-3 1 -4 1 -5 9 -2 6 -5 3","54"]],"created_at":"2026-03-03 11:01:14"}}