406258: GYM102331 H Honorable Mention

Ilya Zban has an array $$$a_1, a_2, \ldots, a_n$$$. A segment $$$[l \ldots r]$$$ of the array is the array $$$a_l, a_{l + 1}, \ldots, a_r$$$.

Ilya has $$$q$$$ ordered triples of the form $$$(l, r, k)$$$, where $$$1 \leq l \leq r \leq n$$$ and $$$1 \leq k \leq r - l + 1$$$. For each such triple, he asked you to answer the following query: "what is the largest sum of sums of elements of $$$k$$$ non-empty non-intersecting subsegments of the segment $$$[l \ldots r]$$$?".

The first line of input contains two integers $$$n$$$ and $$$q$$$: the number of elements in the array and the number of queries ($$$1 \leq n, q \leq 35\,000$$$).

The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$: the given array ($$$-35\,000 \leq a_i \leq 35\,000$$$).

The next $$$q$$$ lines contain queries. Each of them contains three integers $$$l$$$, $$$r$$$, $$$k$$$: the given segment and the number of non-intersecting subsegments on it that you should find ($$$1 \leq l \leq r \leq n$$$, $$$1 \leq k \leq r-l+1$$$).

Output $$$q$$$ integers on separate lines: the answers to the queries.

5 5
-1 2 -3 4 -5
1 5 1
1 5 2
1 5 3
1 5 4
1 5 5

4
6
5
2
-3

5 1
7 7 7 7 7
1 5 1

35