Шляхи з мінімальною вартістю

Пасовище Фермера Джона можна уявити як сітку з квадратних клітинок розміром n * m (подібно до великої шахівниці). Клітинка в рядку x зверху в колонці y позначається як (x, y) для кожного x ∈ [1, n], 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++.

Приклад

Цей же вивід у форматі сітки:

    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|
  *--*--*--*--*

Приклади