Description

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.

Input Format

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 Format

Output a single integer, the maximum profit.

4 2 6 3
1 0
1 0
5 3
20 15
3 2 1 2
4 3 1 2 3

12

Hint

Constraints and Conventions

For all testdata, $N \le 60$, $M \le 240$, $V \le 1000$, $K \le 30$.

Translated by ChatGPT 5