Пути с минимальной стоимостью
Пути с минимальной стоимостью
Пастбище Фермера Джона можно рассматривать решётку из квадратных ячеек размером n * m (как большая шахматная доска). Ячейка в строке x сверху в колонке y обозначается как (x, y) для каждого x ∈ [1, n], y ∈ [1, m]. Далее для каждого y ∈ [1, m], y-ая колонка ассоциируется со стоимостью cy
(1 ≤ cy
≤ 109
).
Беси начинает в ячейке (1, 1). Если она находится в ячейке (x, y), то может выполнить одно из следующих действий:
- Если y < m, Беси может переместиться в следующую колонку (увеличивая y на 1) за цену
x2
. - Если x < n, Беси может переместиться в следующую строку (увеличивая x на 1) за цену
cy
.
Вам даются q независимых запросов, каждый в виде (xi
, yi
) (xi
∈ [1, n], yi
∈ [1, m]), вычислите минимально возможную цену для Беси переместиться из (1, 1) в (xi
, yi
). Вычислите минимально возможную сумму.
Входные данные
Первая строка содержит n и m (2 ≤ n ≤ 109
, 2 ≤ m ≤ 2 * 105
).
Вторая строка содержит m целых чисел c1
, c2
, ..., cm
.
Третья строка содержит q (1 ≤ q ≤ 2 * 105
).
Каждая из последующих q строк содержит два целых числа xi
и yi
.
Выходные данные
Выведите q строк, содержащих ответы на каждый запрос.
Заметим, что ответ требует использования 64-битного целого, например "long long" в C/C++).
Пример
Этот же вывод в формате решётки:
1 2 3 4
*--*--*--*--*
1 | 0| 1| 2| 3|
*--*--*--*--*
2 | 1| 5| 9|13|
*--*--*--*--*
3 | 2|11|20|29|
*--*--*--*--*
4 | 3|19|35|49|
*--*--*--*--*
5 | 4|29|54|69|
*--*--*--*--*
5 4 1 100 100 20 20 1 1 2 1 3 1 4 1 5 1 1 2 2 2 3 2 4 2 5 2 1 3 2 3 3 3 4 3 5 3 1 4 2 4 3 4 4 4 5 4
0 1 2 3 4 1 5 11 19 29 2 9 20 35 54 3 13 29 49 69