기차표

스톡홀름 대중교통은 $12$종류의 승차권을 판매한다. $i$번째 승차권은 정확히 $i$개월 동안 연속으로 유효하다. 승차권의 가격은 매년 종류별로 바뀐다.

Katriel은 최근 $N$년의 가격 자료를 가지고 있으며, 승차권을 가장 적은 비용으로 구매하는 방법을 연구하고 있다. 연도 구간 $a, a+1, \dots, b$가 주어졌을 때, $a$년 1월부터 $b$년 12월까지 모든 달을 빠짐없이 덮는 승차권을 구매하는 최소 비용을 구하려 한다. 이를 계산하는 프로그램을 작성하라.

첫 줄에 정수 $N$ ($1 \le N \le 30\,000$)이 주어진다. 다음 $N$개 줄에는 1년부터 $N$년까지의 가격이 차례대로 주어진다. 각 줄에는 정수 12개가 있으며, 이는 각각 1개월부터 12개월까지 유효한 승차권의 가격이다.

모든 가격은 $0$ 이상 $10\,000$ 이하이다.

다음 줄에 정수 $Q$ ($1 \le Q \le 3\,000$)가 주어진다. 이는 질의의 개수이다. 다음 $Q$개 줄에는 각각 두 정수 $a$, $b$ ($1 \le a \le b \le N$)가 주어지며, 연도 구간 $a, a+1, \dots, b$를 나타낸다.

어느 해에서든 유효 기간이 긴 승차권이 유효 기간이 짧은 승차권보다 싸지 않다.

각 질의 $a, b$에 대해, $a$년 1월에 첫 승차권을 구매했을 때 $a$년 1월부터 $b$년 12월까지 모든 달을 덮는 최소 비용을 한 줄에 출력한다.