Sequence and Queries 33

Given a sequence $A_1, A_2, \ldots, A_N$ of length $N$, write a program that processes the following query.

• l r k: For the subarray $A_l, A_{l+1}, \ldots, A_r$, choose $k$ subarrays from it, and print the maximum possible sum of the elements of the chosen subarrays. Each chosen subarray must be non-empty, and the chosen subarrays must not overlap.

The first line contains the size of the sequence $N$ and the number of queries $M$ ($1 \le N, M \le 35000$).

The second line contains $A_1, A_2, \ldots, A_N$ ($-35000 \le A_i < 35000$).

Each of the next $M$ lines contains one query ($1 \le l \le r \le N$, $1 \le k \le r - l + 1$).

For each query, print the result on its own line.