Job Scheduling with Machine Rental and Purchase Optimization

You are given N jobs and M types of machines. Each machine type can either be rented or purchased. Every job consists of several processes, and each process requires a specific machine type to complete. If a machine type is not purchased, it must be rented for every use.

For each machine type \(i\) (1-indexed), you are given two integers: the rental cost \(R_i\) and the purchase cost \(P_i\). When you choose to rent a machine, each usage in a process costs \(R_i\); if you opt to purchase it, you pay \(P_i\) one time, and then for all processes requiring that machine the cost is waived.

Each job \(j\) provides a revenue \(V_j\) upon completion. Job \(j\) consists of \(K_j\) processes. The \(k\)-th process of job \(j\) requires machine type \(a_{j,k}\) (1-indexed). You may choose any subset \(S\) of jobs to perform. For the selected jobs, for each machine type \(i\) let \(u_i\) denote the total number of times it is used. The cost incurred for machine \(i\) is

\[ \min(R_i \times u_i,\; P_i). \]

Your goal is to maximize the overall profit defined by:

\[ \text{Profit} = \sum_{j \in S} V_j - \sum_{i=1}^{M} \min(R_i \times u_i,\; P_i). \]

inputFormat

The input begins with two integers \(N\) and \(M\) where:

• \(N\) is the number of jobs.
• \(M\) is the number of machine types.

The following \(M\) lines each contain two integers \(R_i\) and \(P_i\) representing, respectively, the rental cost and purchase cost for machine type \(i\) (1-indexed).

Then, for each of the next \(N\) jobs, there are two lines:

• The first line contains two integers \(V_j\) (the revenue for job \(j\)) and \(K_j\) (the number of processes in job \(j\)).
• The second line contains \(K_j\) space-separated integers \(a_{j,1}, a_{j,2}, \dots, a_{j,K_j}\) where each \(a_{j,k}\) (1-indexed) indicates the machine type required for the \(k\)-th process.

outputFormat

Output a single integer representing the maximum profit achievable.

sample

2 2
3 5
2 4
10 2
1 2
8 1
1

11