수열과 쿼리 33

길이가 $N$인 수열 $A_1, A_2, \ldots, A_N$이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• l r k: 부분 수열 $A_l, A_{l+1}, \ldots, A_r$에서 $k$개의 부분 수열을 골라, 고른 부분 수열의 원소 합의 최댓값을 출력하라. 고른 부분 수열은 각각 비어 있지 않아야 하며, 서로 겹쳐서는 안 된다.

첫째 줄에 수열의 크기 $N$과 쿼리의 개수 $M$이 주어진다. ($1 \le N, M \le 35000$)

둘째 줄에는 $A_1, A_2, \ldots, A_N$이 주어진다. ($-35000 \le A_i < 35000$)

셋째 줄부터 $M$개의 줄에 쿼리가 한 줄에 하나씩 주어진다. ($1 \le l \le r \le N$, $1 \le k \le r - l + 1$)

쿼리의 결과를 한 줄에 하나씩 출력한다.