속도 위반

속도 위반은 교통사고의 치명적 결과 가능성을 크게 높이는 위험한 위반이다. 아쉽게도 레이더와 카메라를 이용한 속도 단속은 문제를 완전히 해결하지 못한다. 카메라 앞에서만 속도를 줄이고, 단속이 없는 구간에서는 크게 초과한 속도로 달리는 운전자가 있다. 이런 행동을 막기 위해 도로 통과 시간을 근거로 초과 속도를 확정해 벌금을 부과한다.

n개의 구간으로 이루어진 도로가 있고, 구간은 1번부터 n번까지 번호가 붙어 있다. i번째 구간의 길이는 li미터이다. i번째 구간에는 속도 제한 vi미터/초가 있다.

속도 위반에는 벌금이 부과된다. 초과 정도에 따라 여러 벌금이 정해져 있고, 벌금은 다음과 같이 계산한다.

자동차가 도로 전체에 있는 동안 허용 속도를 초과한 최대량, 즉 매 순간 자동차가 위치한 구간의 최대 허용 속도와 자동차 속도의 차이의 최댓값을 e라 하자. 속도를 초과하지 않았다면 벌금을 부과하지 않는다. 그렇지 않으면 벌금은 다음과 같이 계산한다.

• 0 < e ≤ a1이면 벌금은 f1 화폐 단위이다.
• a1 < e ≤ a2이면 벌금은 f2 화폐 단위이다.
• . . .
• am−2 < e ≤ am−1이면 벌금은 fm−1 화폐 단위이다.
• am−1 < e이면 벌금은 fm 화폐 단위이다.

즉, 초과 속도 구간 m개와 그에 대응하는 벌금이 있다.

자동 벌금 부과 시스템이 q대의 자동차에 대한 데이터를 받았다. 편의상 1번부터 q번까지 번호를 붙이자. i번째 자동차는 si 시각에 도로에 진입해 n개 구간을 모두 통과한 뒤 ti 시각에 도로에서 나갔다. 시간은 도로 개통 시각부터 초 단위로 센다.

시스템은 각 자동차에 대해, 도로 진입 시각과 진출 시각만을 근거로 그 자동차에 확정적으로 부과할 수 있는 최대 벌금을 구해야 한다.

초과 속도 구간 경계, 대응하는 벌금, 자동차의 진입 시각과 진출 시각이 주어질 때 각 자동차에 부과할 수 있는 최대 벌금을 구하는 프로그램을 작성하라.

첫째 줄에는 도로의 구간 수를 나타내는 정수 n이 하나 주어진다 (1 ≤ n ≤ 10).

둘째 줄에는 각 구간의 속도 제한 vi가 n개 주어진다 (1 ≤ vi ≤ 109).

셋째 줄에는 각 구간의 길이 li가 n개 주어진다 (1 ≤ li ≤ 109).

넷째 줄에는 초과 속도 구간 경계의 수를 나타내는 정수 m이 하나 주어진다 (1 ≤ m ≤ 105).

다섯째 줄에는 초과 속도 구간 경계 ai가 m − 1개 주어진다 (1 ≤ ai ≤ 109). ai 값은 엄격히 증가함이 보장된다. m = 1이면 다섯째 줄은 비어 있음에 유의하라.

여섯째 줄에는 초과 속도 구간에 대한 벌금 fi가 m개 주어진다 (1 ≤ fi ≤ 109). fi 값은 증가함이 보장된다.

일곱째 줄에는 처리해야 할 자동차의 수를 나타내는 정수 q가 하나 주어진다 (1 ≤ q ≤ 105).

다음 q개 줄에는 각각 i번째 자동차의 도로 진입 시각과 진출 시각 si, ti가 두 정수로 주어진다 (1 ≤ si < ti ≤ 109).

q대의 자동차 각각에 대해, 도로 진입 시각과 진출 시각만을 근거로 확정적으로 부과할 수 있는 최대 벌금을 한 줄에 하나씩 출력한다. 자동차가 한 번도 허용 속도를 초과하지 않았을 가능성이 있으면 0을 출력한다.

자동차의 진입 시각이나 진출 시각을 10−5 이하로 바꾸어도 부과할 수 있는 벌금이 변하지 않음이 보장된다.