아직 계정이 없으신가요? 회원가입

[21년 재직자 대회 본선] 트럭
난이도
참가자 수
6
제출 수
16
정답률
60.0%
지원 언어
제한시간 : C/C++(2초)/Java/JS/Python(4초)| 메모리 제한 : 1024MB


현대자동차그룹의 트럭 디자이너로 일하는 당신은 신차의 크기를 결정하려고 한다.
총 N명의 소비자에게 신차 구매의사를 조사했다.

i (1≤i≤N)번째 소비자는 Ai개의 제안을 보냈는데, 이 중 j (1≤j≤Ai)번째 제안은 “신차의 크기가 Si,j 이상이라면 차량 한 대를 Pi,j원에 구매할 용의가 있다”는 것이다.

하지만 소비자 각각에 맞춘 차량을 생산하기에는 설비를 위한 비용이 막대해질 것이므로, 신차의 크기를 하나로 결정해야한다.

각 소비자는 트럭을 2대 이상 구매하지는 않을 것이다. 따라서, 당신은 각 소비자마다 그 소비자가 제시한 제안 중 하나를 수락하거나, 그 소비자의 제안을 모두 거절할 것이다. 이 때 당신이 정한 신차의 크기가 소비자의 여러가지 제안을 만족할 수 있다.

당신은 매출에 따라 신차의 크기를 얼마로 설정해야 하는지를 알아보고자, M가지의 시나리오를 고려해 보기로 하였다. 당신은 모든 k (1≤k≤M)에 대해, 총 Qk원의 매출을 내려면, 신차의 크기가 최소 얼마여야 하는지를 구해야 한다.


제약조건
  • 주어지는 모든 수는 정수이다.
  • 1≤N≤100,000
  • 그림6
  • 모든 i,j (1≤i≤N, 1≤j≤Ai)에 대해 1≤Si,j,Pi,j≤109
  • 1≤M≤100,000
  • 모든 k (1≤k≤M)에 대해, 1≤Qk≤109


입력형식
첫 번째 줄에 N이 주어진다. 다음 N개의 줄에는 소비자의 제안에 대한 정보가 주어진다.
이 중 i (1≤i≤N)번째 줄의 형식은 다음과 같다: Ai Si,1 Pi,1 … Si,Ai Pi,Ai
그 다음 줄에 시나리오의 개수 M이 주어진다.
마지막 줄에 M개의 정수 Q1, Q2,…, QM이 공백 하나씩을 사이로 두고 주어진다.


출력형식
M개의 수를 한 칸의 공백을 두고 출력한다. 이 중 k (1≤k≤M)번째 수는
  • Qk원 이상의 매출을 낼 수 있다면, 이 때 신차의 최소 크기이다.
  • Qk원 이상의 매출을 낼 수 없다면, -1이다.


입력예제1
4
1 1 1
1 2 2
1 3 3
1 4 4
10
1 2 3 4 5 6 7 8 9 10


출력예제1
1 2 2 3 3 3 4 4 4 4
  • 신차의 크기가 1이라면, 1번 소비자의 제안만 수락 할 수 있으므로, 총 1원의 매출을 얻을 수 있다.
  • 신차의 크기가 2이라면, 1,2번 소비자의 제안을 수락 할 수 있으므로, 총 1+2=3원의 매출을 얻을 수 있다.
  • 신차의 크기가 3이라면, 1,2,3번 소비자의 제안을 수락 할 수 있으므로, 총 1+2+3=6원의 매출을 얻을 수 있다.
  • 신차의 크기가 4이라면, 모든 소비자의 제안을 수락 할 수 있으므로, 총 1+2+3+4=10원의 매출을 얻을 수 있다.


입력예제2
5
2 10 17 5 19
2 8 7 10 21
3 3 3 9 13 11 14
3 5 3 1 2 9 15
1 9 11
11
21 31 35 54 79 80 100 3 5 7 9


출력예제2
5 8 9 9 10 11 -1 3 3 5 5
일부 시나리오에 대해 설명한다.
신차의 크기가 8일 때, 아래와 같이 제안을 수락하면 총 32원의 매출을 얻을 수 있다.
  • 1번 소비자의 2번 제안(크기 5 이상)을 수락하여, 19원을 얻을 수 있다.
  • 2번 소비자의 1번 제안(크기 8 이상)을 수락하여, 7원을 얻을 수 있다.
  • 3번 소비자의 1번 제안(크기 3 이상)을 수락하여, 3원을 얻을 수 있다.
  • 4번 소비자의 1번 제안(크기 5 이상)과 2번 제안(크기 1 이상)을 모두 만족하므로 더 좋은 조건인 1번 제안을 수락하여, 3원을 얻을 수 있다.

신차의 크기가 10일 때, 아래와 같이 제안을 수락하면 총 79원의 매출을 얻을 수 있다.
  • 1번 소비자의 1번 제안(크기 10 이상)과 2번 제안(크기 5 이상)을 모두 만족하므로 더 좋은 조건인 2번 제안을 수락하여, 19원을 얻을 수 있다.
  • 2번 소비자의 1번 제안(크기 8 이상)과 2번 제안(크기 10 이상)을 모두 만족하므로 더 좋은 조건인 2번 제안을 수락하여, 21원을 얻을 수 있다.
  • 3번 소비자의 1번 제안(크기 3 이상)과 2번 제안(크기 9 이상)을 모두 만족하므로 더 좋은 조건인 2번 제안을 수락하여, 13원을 얻을 수 있다.
  • 4번 소비자의 1번 제안(크기 5 이상)과 2번 제안(크기 1 이상)과 3번 제안(크기 9 이상)을 모두 만족하므로 가장 좋은 조건인 3번 제안을 수락하여, 15원을 얻을 수 있다.
  • 5번 소비자의 1번 제안(크기 9 이상)을 수락하여, 11원을 얻을 수 있다.