← 返回题目列表

Codeforces · 254/E

E. 宿舍

中文机器翻译题面 查看原题

学生Vasya从乡下来到贝尔兰州立大学学习,所以他住在宿舍。一个学期有n天,每一天他的父母都会给他送一些食物。在第 i 天的早上,他收到了 ai 公斤的食物,这些食物可以在当天和第二天食用(然后食物就会变质并变得不适合食用)。

Vasya 每天吃 v 公斤食物。众所周知,瓦夏的父母不允许他挨饿,所以瓦夏总是有足够的食物。 Vasya 有 m 个朋友,有时和他住在一起。让我们对朋友进行索引,从 1 到 m。第 j 号朋友从第 lj 天到第 rj 天(含)与 Vasya 住在一起。另外,第 j 个朋友每天需要 fj 公斤食物。通常瓦夏的朋友们都在食堂吃饭,但有时瓦夏也会慷慨地给他们中的一些人提供食物。瓦夏每天都可以养活一些今天和他住在一起的朋友(或者可能没有养活任何人)。

瓦夏每次喂他的朋友时,他都会给他朋友一天所需的食物,瓦夏在大学的受欢迎程度就会增加一分。瓦夏不能在一天内多次喂同一位朋友。另外,他知道饮食习惯必须有规律,所以他每天总是吃v公斤的食物。

Vasya 希望选择他在学期中每天喂食的对象,以使他的评分尽可能高。原本Vasya的评分是0,因为他是新生。

输入

第一行包含两个整数 n 和 v (1 ≤ n, v ≤ 400)。第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 400),用单个空格分隔。值ai意味着在第i天早上有ai公斤食物进来,该食物在第i天和/或第i+1天适合食用(然后食物变质)。保证瓦夏不喂人的时候,有办法让他吃,每天消耗v公斤的食物。

第三行包含整数 m (1 ≤ m ≤ 400)。以下 m 行中的每一行描述 Vasya 的一个朋友:这些行中的第 j 行包含三个整数 lj、rj、fj (1 ≤ lj ≤ rj ≤ n, 1 ≤ fj ≤ 400),用单个空格分隔。

输出

在第一行打印 Vasya 可以达到的最高评级。在接下来的 n 行中,打印出 Vasya 朋友每天需要吃的食物。在这些行的第 i 行中,首先打印第 i 天喂养的朋友数量,然后列出这些朋友的索引。以任意顺序打印这些列表中的好友。如果有多个最优解,则打印其中任意一个。

示例

输入 #1

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

输出 #1

7
1 2
1 2
3 2 1 3
2 2 3