적은 시간, 많은 이익

도시 계획가들은 $M$개의 상점이 있는 도시에 $N$개의 공장을 지을 계획을 세웠다. 각 공장은 짓거나 계획 단계로 남겨둘 수 있다.

각 상점은 운영을 위해 정해진 공장 집합의 제품을 필요로 한다. 상점 $j$가 필요로 하는 모든 공장이 지어지면, 그 상점은 $\mathit{pro}_j$ 단위의 일회성 이익을 즉시 얻는다. 공장을 한 번 지으면 그 공장에 의존하는 모든 상점을 지원할 만큼 충분한 제품을 생산한다.

$i$번째 공장을 짓는 데는 $\mathit{pay}_i$ 단위의 투자가 필요하고 $t_i$일이 걸린다. 두 개 이상의 공장을 동시에 지을 수 있으므로, 여러 공장을 짓는 데 걸리는 시간은 각 공장의 건설 시간 $t_i$ 중 최댓값이다.

도시 계획가들은 모든 공장을 지을 자원은 충분하지만, 순이익을 내고 싶어 한다. 구체적으로, 운영되는 상점의 총이익에서 지은 공장의 총비용을 뺀 값이 $L$ 단위 이상이 되도록 공장의 부분집합을 골라 짓거나, 그것이 불가능하다는 것을 알아내려 한다.

먼저, $t$일 안에 $L$ 단위 이상의 이익을 낼 수 있는 가장 작은 일수 $t$를 구한다. 그다음, $t$일 안에 낼 수 있는 가장 큰 이익 $p$를 구한다.

첫째 줄에 세 정수 $N$, $M$, $L$이 주어진다. 각각 지을 수 있는 공장의 수, 상점의 수, 요구되는 이익이다 ($1 \le N, M \le 200$, $1 \le L \le 10^9$).

이어서 $N$개의 줄이 주어진다. 각 줄은 공장 하나를 나타내며 두 정수 $\mathit{pay}_i$와 $t_i$를 포함한다. 각각 $i$번째 공장의 투자 금액과 건설 시간이다 ($1 \le \mathit{pay}_i \le 3 \cdot 10^4$, $1 \le t_i \le 10^9$).

그다음 $M$개의 줄이 주어진다. 각 줄은 상점 하나를 나타내며 정수 $\mathit{pro}_j$로 시작한다 ($1 \le \mathit{pro}_j \le 1.2 \cdot 10^5$). 이어서 상점 $j$가 운영되는 데 필요한 공장의 수를 나타내는 정수 $k_j$가 주어진다 ($0 \le k_j \le N$). 그다음에는 상점 $j$가 운영되는 데 필요한 공장의 번호 $\mathit{plant}_{j, 1}$, $\mathit{plant}_{j, 2}$, $\ldots$, $\mathit{plant}_{j, k_j}$가 서로 다른 $k_j$개의 정수로 주어진다 ($1 \le \mathit{plant}_{j, r} \le N$).

조건을 만족하는 계획이 있으면 두 정수 $t$와 $p$를 출력한다. $t$는 $L$ 단위 이상의 이익을 낼 수 있는 가장 작은 일수이고, $p$는 $t$일 안에 낼 수 있는 최대 이익이다.

$L$ 단위 이상의 이익을 내는 계획이 없으면 "impossible"을 출력한다.