初めに

この問題はBreaking door keys（ALL BREAK ver.）と問題文が同じですが、$K_i$ の制約が異なっています。

問題文

$N$ 個のドアが横一列に並んでいます。ドア $i$ には強さ $S_i$ の鍵が付けられています。

これから、以下の問題について考えます。

これから、$l\leq i\leq r$ を満たすドア $i$ の内 $k$ 個を選び、その鍵を破壊します。

このとき、破壊したドアの鍵の強さの総和だけ体力を消費します。具体的には、ドア $p_1,p_2,...,p_k$ の鍵を壊した時、体力を $\displaystyle\sum_{i=1}^k S_{p_i}$ 消費します。

適切なドアを選んだ時、それらのドアの鍵を壊すために必要な体力の最小値を求めてください。

この問題には $Q$ 個のシチュエーションが考えられます。$i$ 個目のシチュエーションでは $l=L_i,r=R_i,k=K_i$ としてこの問題を答えてください。

制約

• $1\leq N\leq 10^5$
• $1\leq Q\leq 10^5$
• $1\leq S_i\leq 10^9$
• $1\leq L_i\leq R_i\leq N$
• $\color{red}{1\leq K_i \leq \min(10,R_i-L_i+1)}$
• 入力はすべて整数

小課題

この問題にはサブタスクによる部分点が設定されています。

入力

$N\ Q$
$S_1\ S_2\ \dotsc \ S_N$
$L_1\ R_1\ K_1$
$L_2\ R_2\ K_2$
$\vdots$
$L_Q\ R_Q\ K_Q$

出力

$Q$ 行出力してください。

$i$ 行目には $i$ 個目のシチュエーションに対する答えを出力してください。

サンプル

6 3
1 6 9 2 3 1
1 3 2
2 4 1
1 6 2

7
2
2

6 3
4 1 1 8 9 2
4 6 1
2 3 1
1 6 1

2
1
1

6 3
3 1 4 1 5 9
1 5 3
1 4 4
1 6 2

5
9
2