연습문제

[21년 재직자 대회 본선] 트럭

난이도
Lv. 4
제출
107 명
참가자
16 명
정답률
32.14 %
지원 언어
C
C++
Java
Python
JavaScript
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
JavaScript 4초 1024MB
C 2초 1024MB
C++ 2초 1024MB
Java 4초 1024MB
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


모든 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원을 얻을 수 있다.

목록