（Ważna wiadomość）

• 题目编号：WWI
• 来源：ONTAK 2026 Day 2
• 难度估计：CF 3200～3400
• 筛选结论：CF 2200+
• 原题页面：https://sio2.mimuw.edu.pl/c/wiekuisty-ontak-2026/p/wwi/

难度为按 Codeforces 体系进行的非官方估计。

题目描述

重要消息：把这题做掉。

给定一个长度为 $n$ 的整数序列 $x_1,x_2,\ldots,x_n$，以及 $q$ 个询问。

第 $i$ 个询问由三个整数 $a_i,b_i,k_i$ 组成。

你需要回答：在区间 $[a_i,b_i]$ 内，最多选择 $k_i$ 个两两不相交的连续子区间，这些子区间中所有元素的总和最大可以是多少？

两个子区间被认为不相交，当且仅当它们没有共同的数组位置。

允许选择少于 $k_i$ 个子区间，因此如果所有选择都会使答案变差，也可以不选择相应的负贡献区间。

输入格式

第一行包含两个整数 $n,q$：

$1\le n,q\le75000$。

第二行包含 $n$ 个整数 $x_1,x_2,\ldots,x_n$，满足：

$|x_i|\le35000$。

接下来 $q$ 行，每行包含三个整数 $a_i,b_i,k_i$：

• $1\le a_i\le b_i\le n$；
• $1\le k_i\le b_i-a_i+1$。

输出格式

按输入顺序输出每个询问的答案，每个答案占一行。

样例

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

4
6
6

子任务