0 Judge
Code: 0
「時曲,你不要理會那些傢伙。他們只是因為比不過你,所以嫉妒你」基德安慰著你說道。
你懷疑世間所有的序列,
任何序列維護的資料都想反駁
對任何子序列完全不......
嗯,總之,你想要多次詢問,一個序列在從其區間$[l,r]$中最多選$k$個元素的限制下,選的元素總和最多為何。同個位置的元素最多只能選一次。選的元素數量若為0,則總和為0。
可能有反社會人格的你決定自己的詢問由自己來回答。
第一行給定兩個整數$N(1\leq N\leq 10^5)$與$Q(1\leq Q\leq 10^5)$,表示序列的大小與詢問的數量。
第二行有$N$個整數$a_1,a_2...a_N(0\leq |a_i|\leq 10^5)$,表示序列的各元素。
接下來有$Q$行,每行給定三個整數$l,r,k(1\leq l\leq r\leq N,0\leq k\leq N)$,表示詢問從序列區間$[l,r]$中拿出最多$k$個元素可以得到的最大總和為何。
對於每筆詢問,輸出可以得到的最大總和,並換行。
5 5
1 -2 3 4 5
3 5 1
3 5 2
3 5 4
1 3 3
2 2 5
5
9
12
4
0
子任務一($5\%$):$N,Q\leq 500$
子任務二($10\%$):$a_i\geq 0$且所有詢問的$k=N$
子任務三($13\%$):所有詢問的$k=3$
子任務四($32\%$):$N,Q\leq 10^4$
子任務五($40\%$):無限制