Description

Caesar leads a mercenary troop of $n$ people who take jobs from the Venetian Trading House.

The troop is diverse: different people have different skills, and some have multiple skills.

The jobs vary a lot. Some require several people to cooperate; some can be done by a single person. Some are simple, take little time, and thus pay less; others are difficult, require many people to work together for a long period, and thus pay more. Each job lasts no more than one month. A person cannot work on two jobs at the same time, and cannot join or leave a job midway. However, a person may stay idle and do no job.

For a job that requires $p$ people, if the number of assigned people is $x > p$, then the payment becomes the original payment divided by $(x - p + 1)$. If $x < p$, the job cannot be completed. Only people who are capable of a job may be assigned to that job.

Caesar holds a military meeting at the end of each month to summarize the results, pay everyone, and assign the next month’s jobs.

How should Caesar assign the jobs to maximize the total payment? What is the maximum total payment?

Input Format

• The first line contains two positive integers $n$ and $m$, separated by a space, where $n < 10$ is the number of mercenaries and $m < 15$ is the number of available jobs for the next month.
• The next $n$ lines describe the capabilities of each mercenary. On line $i$ (corresponding to mercenary $i$), the first integer $k_i$ satisfies $0 \le k_i \le m$ and denotes how many jobs mercenary $i$ can perform. It is followed by $k_i$ distinct integers, the IDs of the jobs that mercenary $i$ can perform, separated by spaces.
• The last $m$ lines describe the jobs. On line $j$ (corresponding to job $j$), there are four integers $b$, $e$, $p$, and $r$, separated by spaces:
  • $0 < b < 32$: the start day (this day is counted in the job duration),
  • $0 < e < 32$: the end day (this day is also counted in the job duration),
  • $p < 10$: the required number of people,
  • $0 < r < 100000$: the payment for the job.

Output Format

The first line contains a single integer $t$, the maximum total payment that can be obtained.

3 5
2 1 4
2 2 4
3 3 4 5
2 20 1 100 
1 18 1 200 
3 28 1 800 
21 30 3 1500 
19 21 1 400 

1800

Hint

Translated by ChatGPT 5