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

총 N명의 소비자에게 신차 구매의사를 조사했다.

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

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

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

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