P1860 New Magic Potion

There are $N$ types of potions in a shop. Each potion has a selling price and a buyback price. Xiao S has $V$ units of money and knows $M$ spells that can combine some potions into another potion. He can use at most $K$ spells in one day. What is the maximum profit he can make in one day? Note: Money earned from selling cannot be reinvested.

The first line contains four integers $N, M, V, K$. The next $N$ lines each contain two integers, the selling price and the buyback price of a potion. The next $M$ lines each contain several integers: the first integer is the product potion’s ID, the second integer is the number of ingredient types, followed by the IDs of the ingredient potions.

Output a single integer, the maximum profit.

### Constraints and Conventions For all testdata, $N \le 60$, $M \le 240$, $V \le 1000$, $K \le 30$. Translated by ChatGPT 5