Пастбище Фермера Джона можно рассматривать решётку из квадратных ячеек размером n * m (как большая шахматная доска). Ячейка в строке x сверху в колонке y обозначается как (x, y) для каждого x ∈ [1, n], y ∈ [1, m]. Далее для каждого y ∈ [1, m], y-ая колонка ассоциируется со стоимостью c[y]
(1 ≤ c[y]
≤ 10^9
).
Беси начинает в ячейке (1, 1). Если она находится в ячейке (x, y), то может выполнить одно из следующих действий:
Если y < m, Беси может переместиться в следующую колонку (увеличивая y на 1) за цену x[2]
.
Если x < n, Беси может переместиться в следующую строку (увеличивая x на 1) за цену c[y]
.
Вам даются q независимых запросов, каждый в виде (x[i]
, y[i]
) (x[i]
∈ [1, n], y[i]
∈ [1, m]), вычислите минимально возможную цену для Беси переместиться из (1, 1) в (x[i]
, y[i]
). Вычислите минимально возможную сумму.
Первая строка содержит n и m (2 ≤ n ≤ 10^9
, 2 ≤ m ≤ 2 * 10^5
).
Вторая строка содержит m целых чисел c[1]
, c[2]
, ..., c[m]
.
Третья строка содержит q (1 ≤ q ≤ 2 * 10^5
).
Каждая из последующих q строк содержит два целых числа x[i]
и y[i]
.
Выведите q строк, содержащих ответы на каждый запрос.
Заметим, что ответ требует использования 64-битного целого, например "long long" в C/C++).
Этот же вывод в формате решётки: