최적의 트럭

Peter는 트럭을 한 대 사서 작은 운송 사업을 시작하려 한다. 시장을 조사한 결과, 도시에 $n$명의 잠재 고객이 있다는 것을 알아냈다. $i$번째 고객에게는 $m_i$개의 계약 선택지가 있다. 각 선택지는 두 수로 주어진다. $w_{ij}$는 계약을 이행하는 데 필요한 트럭의 최소 적재량이고, $c_{ij}$는 Peter가 이 계약을 체결했을 때 얻는 이익이다. 각 고객과는 계약을 최대 하나만 체결할 수 있다.

이제 Peter는 원하는 이익을 얻으려면 어떤 트럭을 사는 것이 좋을지 고민하고 있다. 선택지는 $q$개이다. $i$번째 선택지에서 Peter는 이익이 최소 $x_i$ 이상이기를 원한다. 각 선택지마다 그러한 이익을 얻을 수 있는 트럭 적재량의 최솟값을 구해 주자.

첫째 줄에 정수 $n$이 주어진다 ($1\le n\le 10^5$).

이어서 각 잠재 고객의 계약 선택지를 설명하는 $n$개의 블록이 주어진다. 각 블록은 수 $m_i$로 시작하고, 이어서 $m_i$쌍의 수 $w_{ij}, c_{ij}$가 주어진다 ($1\le m_i$, $\sum m_i \le 5 \cdot 10^5$, $1\le w_{ij}, c_{ij}\le 10^9$).

다음으로 수 $q$가 주어진다 ($1\le q\le 10^5$). 이어서 $q$개의 수 $x_i$가 주어진다 ($1\le x_i\le 10^9$).

각 선택지마다 필요한 이익을 얻을 수 있는 트럭 적재량의 최솟값을 $q$개 출력한다. 필요한 이익을 얻을 수 없으면 해당 선택지에 대해 $-1$을 출력한다.