Dormitory

题意翻译

有 $n$ 天，第 $i$ 天你会收到 $a_i$ 份食物。食物有保质期，第 $i$ 天收到的食物只能在第 $i$ 天和第 $i+1$ 天食用。 你还有 $m$ 个朋友。第 $i$ 个朋友会在第 $l_i$ 至 $r_i$ 天拜访你，食量是 $c_i$ 份食物。 你每天可以选择一些朋友供应食物（必须供给正好 $c_i$ 份食物，一个朋友一天只能供给一次），每贡献一人次你的人气值就会 $+1$。 同时，你每天必须吃 $v$ 份食物。 问你 $n$ 天后你的人气值最大是多少。 Translated by paulzrm

题目描述

Student Vasya came to study in Berland State University from the country, so he is living in a dormitory. A semester has $ n $ days, and in each of those days his parents send him some food. In the morning of the $ i $ -th day he receives $ a_{i} $ kilograms of food that can be eaten on that day and on the next one (then the food goes bad and becomes unfit for consumption). Every day Vasya eats $ v $ kilograms of food. It is known that Vasya's parents do not allow him to starve, so there always is enough food for Vasya. Vasya has $ m $ friends who sometimes live with him. Let's index the friends from 1 to $ m $ . Friend number $ j $ lives with Vasya from day $ l_{j} $ to day $ r_{j} $ , inclusive. Also, the $ j $ -th friend requires $ f_{j} $ kilograms of food per day. Usually Vasya's friends eat in the canteen, but sometimes generous Vasya feeds some of them. Every day Vasya can feed some friends who live with him this day (or may feed nobody). Every time Vasya feeds his friend, he gives him as much food as the friend needs for the day, and Vasya's popularity rating at the University increases by one. Vasya cannot feed the same friend multiple times in one day. In addition, he knows that eating habits must be regular, so he always eats $ v $ kilograms of food per day. Vasya wants so choose whom he will feed each day of the semester to make his rating as high as possible. Originally Vasya's rating is 0 because he is a freshman.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ v $ ( $ 1<=n,v<=400 $ ). The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=400 $ ), separated by single spaces. Value $ a_{i} $ means that in the morning of the $ i $ -th day $ a_{i} $ kilograms of food come, the food is good for eating on day $ i $ and/or on day $ i+1 $ (then the food goes bad). It is guaranteed that if Vasya doesn't feed anyone, there is a way for him to eat so as to consume $ v $ kilograms of food every day. The third line contains integer $ m $ ( $ 1<=m<=400 $ ). Each of the following $ m $ lines describes one Vasya's friend: the $ j $ -th of these lines contains three integers $ l_{j},r_{j},f_{j} $ ( $ 1<=l_{j}<=r_{j}<=n,1<=f_{j}<=400 $ ), separated by single spaces.

输出格式

In the first line print the highest rating Vasya can reach. In the next $ n $ lines print, which friends Vasya needs to feed on each day. In the $ i $ -th of these lines first print the number of friends to feed on the $ i $ -th day, and then list the indexes of these friends. Print the friends in these lists in any order. If there are multiple optimal solutions, print any of them.

输入输出样例

输入样例 #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