CF254E Dormitory

学生 Vasya 从乡下来到 Berland 国立大学上学，因此住在宿舍里。一个学期有 $n$ 天，每天他的父母都会给他寄一些食物。在第 $i$ 天早上，他会收到 $a_i$ 千克的食物，这些食物可以在当天和第二天食用（再往后食物就会变质而不能再食用了）。 Vasya 每天需要吃 $v$ 千克食物。已知 Vasya 的父母不允许他挨饿，所以 Vasya 总是有足够的食物可供食用。Vasya 有 $m$ 个朋友，有时这些朋友会和他一起住。我们用从 $1$ 到 $m$ 的编号来标记这些朋友。第 $j$ 个朋友会在 $l_j$ 到 $r_j$（包括两天）与 Vasya 同住。此外，第 $j$ 个朋友每天需要 $f_j$ 千克食物。通常情况下，Vasya 的朋友们会去食堂吃饭，但有时慷慨的 Vasya 会招待其中一些朋友。每天，Vasya 可以选择给当天与他同住的朋友中的部分人或全部人提供食物（也可以不招待任何人）。 每当 Vasya 给一位朋友提供食物时，他会给该朋友当天所需的全部食物，且 Vasya 在大学的受欢迎度会提升 $1$。同一天内，Vasya 不能为同一个朋友提供多次食物。此外，Vasya 的饮食习惯必须规律，他每天都要吃 $v$ 千克食物。 Vasya 想要决定每天给哪些朋友提供食物，以使他的受欢迎度尽可能高。最初 Vasya 的受欢迎度为 $0$，因为他是新生。

第一行包含两个整数 $n$ 和 $v$（$1 \leq n, v \leq 400$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 400$），以单个空格分隔。$a_i$ 表示在第 $i$ 天早晨收到的食物千克数，这些食物可以在第 $i$ 天和第 $i+1$ 天食用（之后食物会变质）。保证如果 Vasya 不招待任何人，他每天都能吃到 $v$ 千克食物。 第三行包含一个整数 $m$（$1 \leq m \leq 400$）。接下来的 $m$ 行每行描述一个朋友：第 $j$ 行包含三个整数 $l_j, r_j, f_j$（$1 \leq l_j \leq r_j \leq n, 1 \leq f_j \leq 400$），以单个空格分隔。

第一行输出 Vasya 能达到的最高受欢迎度。 接下来的 $n$ 行，每行输出第 $i$ 天需要招待的朋友编号。对于第 $i$ 天，先输出当天需要招待的朋友数，然后输出这些朋友的编号，编号顺序任意。如果存在多组最优解，输出任意一种即可。

由 ChatGPT 5 翻译