| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 57 | 1 | 1 | 50.000% |
The Stockholm public transport system offers 12ドル$ kinds of tickets for purchase. The $i$'th kind of ticket is valid for exactly $i$ consecutive months. However, they also change the price of every kind of ticket every year.
Katriel has access to the pricing data for the last $N$ years, and is currently studying the complexity of purchasing your tickets in order to minimize costs. More precisely he wants to determine, given an interval of years $a, a + 1, \dots, b,ドル what the cost is to purchase tickets starting from January in year $a$ that are valid every month to December in year $b$. Can you write a program to determine this?
The first line of input contains the integer 1ドル \le N \le 30,000円,ドル the number of years Katriel has pricing data for. The next $N$ lines contain the pricing data for years 1,ドル 2, \dots, N,ドル in order. The pricing data for a given year is given as 12ドル$ integers: the prices of the tickets valid for 1,ドル 2, \dots, 12$ months, respectively. All prices are between 0ドル$ and 10ドル,000円$.
The next line contains the integer 1ドル \le Q \le 3,000円,ドル the number of intervals of years Katriel wishes to compute the price for. The next $Q$ lines contains each of these intervals, given as two integers 1ドル \le a \le b \le N$ representing the interval $a, a + 1, \dots, b$.
In a given year, a ticket valid for a longer period of time is never cheaper than a ticket valid for a shorter period of time.
For each query $a, b,ドル output a single line containing the minimum cost to purchase tickets valid during the entire interval, given that the first ticket is bought in January in year $a$.
3 1 2 3 4 5 6 7 8 9 10 11 12 2 3 4 5 6 7 8 9 10 11 12 13 3 4 5 6 7 8 9 10 11 12 13 14 6 1 1 2 2 3 3 1 2 2 3 1 3
12 13 14 25 27 39