P4177 [CEOI 2008] order

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.

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$.

The maximum profit.

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