32448번 - 서울과 학기-술 대학교 스페셜 저지

문제

현재 공릉동에는 서울과학기술대학교가 위치해 있습니다. 하지만, 어떤 평행세계의 공릉동에는 "서울과 학기-술 대학교"가 있습니다.

"서울과 학기-술 대학교"에 재학 중인 대학생인 카프리는 현재 수강할 과목을 결정하는 데 어려움을 겪고 있습니다. 그도 그럴 것이, 서울과학기술대학교의 최대 평점은 4ドル.5$이지만, "서울과 학기-술 대학교"의 최대 평점은 10ドル,円 000.0$입니다. 그래서 교수 또한 각 학생에게 0ドル$ 이상 10ドル,円 000$ 이하의 정수로 평점을 매깁니다.

각 과목은 15ドル$ 이하의 자연수인 학점 $H$와 10ドル,円 000$ 이하의 음이 아닌 정수인 예상 평점 $P$를 가지고 있습니다. $k$개의 과목을 수강하였을 때 각 과목의 학점이 $h_1,h_2,\cdots ,h_k$이고 평점이 $p_1,p_2,\cdots ,p_k$라면, 학기 최종 평점은 다음과 같습니다.

$$\frac{{h_1p_1+h_2p_2+\cdots +h_kp_k}}{{h_1+h_2+\cdots +h_k}}$$

카프리는 여러 가지 시나리오를 고려하여 이번 학기 시간표를 정하려고 합니다. 카프리가 고려할 시나리오의 종류는 다음과 같습니다.

• $l,円,円 r$: 이번 학기에는 모든 과목을 합쳐 총 $l$학점 이상 $r$학점 이하의 학점을 얻어야 합니다.

"서울과 학기-술 대학교"의 교칙에 따라 모든 재학생은 각 학기 최대 $L$학점을 수강할 수 있습니다. 또한, 어떤 과목도 수강하지 않을 경우 제적될 수 있으므로, 모든 재학생은 각 학기 적어도 1ドル$학점 이상을 수강해야 합니다. 다시 말해, 각 시나리오에 대해 1ドル\le l\le r\le L$이 성립합니다.

카프리가 모든 과목에 대해 평점을 예상한 대로 정확하게 받을 수 있다고 가정할 때, 각 시나리오에 대해 카프리의 학기 최종 평점의 최댓값을 구해 주세요.

입력

첫 번째 줄에 수강할 수 있는 과목의 수 $n$과 학점 제한 $L$이 공백으로 구분되어 주어집니다. (1ドル\le n\le 10^5,ドル 1ドル\le L\le 5\cdot 10^5$)

두 번째 줄부터 $n$개의 줄에 걸쳐 과목의 정보가 주어집니다.

$n$개의 줄 각각에는 각 과목의 학점 $H_i$와 수강하였을 때의 평점 $P_i$가 공백으로 구분되어 주어집니다. (1ドル\le H_i\le 15,ドル 0ドル\le P_i\le 10,円 000$)

$n+2$번째 줄에 시나리오의 개수 $q$가 주어집니다. (1ドル\le q\le 10^5$)

그다음 줄부터 $q$개의 줄에 걸쳐 시나리오의 정보가 주어집니다.

$q$개의 줄 각각에는 시나리오를 나타내는 두 정수 $l_i$와 $r_i$가 공백으로 구분되어 주어집니다. (1ドル\le l_i\le r_i\le L$)

출력

주어진 시나리오 각각에 대해 카프리가 얻을 수 있는 학기 최종 평점의 최댓값을 새로운 줄에 출력합니다.

단, 총 학점이 $l_i$학점 이상 $r_i$학점 이하가 되도록 수강 신청을 할 수 있는 방법이 없다면 0ドル$을 출력합니다.

모든 시나리오에 대해 정답과 출력한 값 간의 절대 오차 또는 상대 오차가 10ドル^{-6}$ 이하인 경우 정답으로 인정됩니다.

제한

힌트