Tnine

Kongyi found a company called Tnine after graduation, and she has eight employees. With her effort, the company expands gradually. However, there are also some problems. For example, she doesn't know how to arrange those employees to get the maximum profits. If you can help the inexperienced kongyi, she will be appreciated.

Now I will give you the workflow of Tnine in T days, the company has received N projects’ requests, but it need not to accept all.

Each project will give four conditions 1) It will needs M employees;2) It must be started on the day S and finished on the day E. Meantime, it can not be interrupted;3) The project can offer P profits. 4) You can assume in one day will not have more than one project.

Each employee who joins a project will get a day off after finishing the work, it means Kongyi will not ask an employee to join a new project in the second day after he finished his project. And Kongyi knows some of workers’ cooperation will get extra profits. Now your job is to help Kongyi to arrange the eight employees and choose which projects to accept to maximize the total profits.

The input may contain several data sets.
The first line of each test case contains two integers T (0 < T ≤ 100000) and N (0 < N ≤ 500). Then following N lines give the description of the projects. Each line contains four non-negative integers M (0 < M ≤ 8), S, E (0 < S, E ≤ T) and P. With the same meaning described above.

The next line contains a single integer Q (0 ≤ Q < 2^8), denotes Q descriptions of cooperation as following.
Each description is a single line, the first integer q shows the number of employees in this cooperation. Then the following q integers mean those q employees’ id (0 ≤ id < 8) and the last integer means the extra profits F. That means a team contains those employees will take extra profits F.

Note that if a team contains more than one kind of cooperation, we will chose the maximum extra profits to add.
See the sample input for further details.

For each test case, output one line containing the maximum profits Tnine will gain during the T days.

10 3
3 2 5 2
3 6 7 1
8 9 10 2
2
3 1 3 7 2
3 4 5 3 1

15 3
3 1 5 3
6 6 7 1
2 8 11 1
2
4 2 5 6 3 3
2 2 3 2

10 1
4 1 10 1
2
3 0 1 2 1
3 1 2 3 2

9
8
3

木雪空亦

HDU 2nd “Vegetable-Birds Cup” Programming Open Contest