Description

There are $N$ jobs and $M$ types of machines. Each type of machine can either be rented or purchased. Each job consists of several operations, and each operation requires a certain type of machine to complete.

You need to maximize the profit.

Input Format

The first line gives $N, M$.

Then, for each of the $N$ jobs:

• The first line gives $x_i$ and $t_i$, denoting the revenue of this job and the number of operations, respectively.
• The next $t_i$ lines each contain two integers $a_{ij}$ and $b_{ij}$, denoting the machine required for this operation and the cost of renting this machine for this job, respectively.

Finally, the last $M$ lines each contain a positive integer $y_i$, denoting the cost of purchasing machine $i$.

Output Format

The maximum profit.

2 3
100 2
1 30
2 20
100 2
1 40
3 80
50
80
110

50

Hint

Constraints: For $100\%$ of the testdata, $1 \le N, M \le 1200$, $1 \le x_i \le 5000$, $b_{ij}, y_i \le 20000$.

Translated by ChatGPT 5