문제

현대차그룹의 트럭 디자이너로 일하는 당신은 신차의 크기를 결정하려고 한다.

총 명의 소비자가 신차 구매 의사를 보였다. ()번째 소비자는 개의 제안을 보냈는데, 이 중 ()번째 제안은 "신차의 크기가 이상이라면 차량 한 대를 원에 구매할 용의가 있다"는 것이다.

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

하지만 소비자 각각에 맞춘 차량을 생산하기에는 설비를 위한 비용이 막대해질 것이므로, 모든 소비자에게 같은 크기의 차량을 제공해야 한다.

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

입력

첫 번째 줄에 이 주어진다.

다음 개의 줄에는 소비자의 제안에 대한 정보가 주어진다. 이 중 ()번째 줄의 형식은 다음과 같다:

그 다음 줄에 시나리오의 개수 이 주어진다.

마지막 줄에 개의 정수 , , , 이 공백 하나씩을 사이로 두고 주어진다.

• 주어지는 모든 수는 정수이다.
• 모든 (, )에 대해
• 모든 ()에 대해,

출력

개의 수를 출력한다. 이 중 ()번째 수는:

• 원 이상의 매출을 낼 수 있다면, 이 때 신차의 최소 크기이다.
• 원 이상의 매출을 낼 수 없다면, 이다.

서브태스크

1. 서브태스크 1 (10점)
   • 모든 (, )에 대해
   • 모든 ()에 대해,
2. 서브태스크 2 (15점)
   • 모든 (, )에 대해
   • 모든 ()에 대해,
3. 서브태스크 3 (35점)
4. 서브태스크 4 (40점)
   • 추가 제약 조건 없음.

노트

예제 1번 설명:

• 신차의 크기가 1이라면, 1번 소비자에게만 차량을 보낼 수 있으므로, 총 1원의 매출을 얻는다.
• 신차의 크기가 2이라면, 1,2번 소비자에게만 차량을 보낼 수 있으므로, 총 원의 매출을 얻는다.
• 신차의 크기가 3이라면, 1,2,3번 소비자에게만 차량을 보낼 수 있으므로, 총 원의 매출을 얻는다.
• 신차의 크기가 4이라면, 모든 소비자에게 차량을 보낼 수 있으므로, 총 원의 매출을 얻는다.

예제 2번 설명:

일부 시나리오에 대해 설명한다.

신차의 크기가 8일 때, 아래와 같이 제안을 수락하면 31원의 매출을 얻을 수 있다.

• 1번 소비자의 2번 제안(조건: 신차 크기 5 이상)을 수락하여, 19원을 받는다.
• 2번 소비자의 1번 제안(조건: 신차 크기 8 이상)을 수락하여, 7원을 받는다.
• 3번 소비자의 1번 제안(조건: 신차 크기 3 이상)을 수락하여, 3원을 받는다.
• 4번 소비자의 2번 제안(조건: 신차 크기 1 이상)을 수락하여, 2원을 받는다.

신차의 크기가 9일 때, 아래와 같이 제안을 수락하면 55원의 매출을 얻을 수 있다.

• 1번 소비자의 2번 제안(조건: 신차 크기 5 이상)을 수락하여, 19원을 받는다.
• 2번 소비자의 1번 제안(조건: 신차 크기 8 이상)을 수락하여, 7원을 받는다.
• 3번 소비자의 1번 제안(조건: 신차 크기 3 이상)을 수락하여, 3원을 받는다.
• 4번 소비자의 3번 제안(조건: 신차 크기 9 이상)을 수락하여, 15원을 받는다.
• 5번 소비자의 1번 제안(조건: 신차 크기 9 이상)을 수락하여, 11원을 받는다.