| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 256 MB | 14 | 11 | 8 | 72.727% |
There are $n$ boxes (numbered 1ドル$ through $n$), $m$ keys (numbered 1ドル$ through $m$), and $d$ shops (numbered 1ドル$ through $d$). The key $i$ can be used to open one of the boxes $a_{i,1}, \ldots, a_{i,k_i}$. However, once a key is used to open a box, it disappears. Thus, a key can't be used to open multiple boxes. The key $i$ is sold at the shop $s_i,ドル and its price is $c_i$ dollars. Akiba wants to buy some keys and open all the boxes. (He can't buy the same key multiple times.)
Kitamasa wants to prevent Akiba from doing this. In order to do it, he can change the prices of some keys before Akiba decides which keys to buy. If he pays $b_j$ dollars, he can increase the prices of all keys sold at the shop $j$ by one dollar. For each shop, he can repeat this any non-negative integer number of times: for example, if he pays 2ドル b_j$ dollars, he can increase the prices of all keys sold at the shop $j$ by two dollars. However, for example when $b_j = 2,ドル he can't pay 1ドル$ dollar and change the prices by 0ドル.5$ dollars.
Akiba's objective is to minimize the value (Akiba's payment) $-$ (Kitamasa's payment), and Kitamasa's objective is to maximize it. Compute this value when the two players play optimally. If the answer can be infinitely large, print $-1$. It is guaranteed that if Kitamasa does nothing, Akiba can open all boxes.
The first line of input contains three integers $n,ドル $m,ドル and $d$ (1ドル \le m \le 1000,ドル $n \le 100,ドル 1ドル \le n, d \le m$).
Then $m$ lines follow, each describing one key. Each line starts with three integers: $c_i,ドル the price of the key, $s_i,ドル the number of the shop where the key is sold, and $k_i,ドル the number of boxes this key can open. Then $k_i$ integers follow: the numbers of these boxes (1ドル \le c_i \le 1000,ドル 1ドル \le s_i \le d,ドル 1ドル \le k_i \le \min (10, n),ドル 1ドル \le a_{i,j} \le n,ドル and if $j \ne k,ドル $a_{i,j} \ne a_{i,k}$).
Then $d$ lines follow, each containing one integer $b_i$ (1ドル \le b_i \le 1000$).
Print one integer: the answer to the problem.
3 4 1 2 1 2 1 2 2 1 2 2 3 2 1 2 3 1 3 1 3 1 2 3 5
6
3 4 1 2 1 2 1 2 2 1 2 2 3 2 1 2 3 1 3 1 3 1 2 3 2
-1
2 3 2 3 1 2 1 2 4 1 1 2 5 2 2 1 2 1 2
8