Пастбище Фермера Джона можно рассматривать решётку из квадратных ячеек
размером \(N\times M\) (\(2\le N\le 10^9\), \(2\le M\le 2\cdot 10^5\))
(как большая шахматная доска). Ячейка в строке \(x\) сверху в колонке \(y\)
обозначается как \((x,y)\) для каждого \(x\in [1,N], y\in [1,M]\).
Далее для каждого \(y\in [1,M]\), \(y\)-ая колонка ассоциируется со стоимостью
\(c_y\) (\(1\le c_y\le 10^9\)).
Беси начинает в ячейке \((1,1)\). Если она находится в ячейке \((x,y)\),
она может выполнить одно из следующих действий:
- Если \(y<M\), Беси может переместиться в следующую колонку
(увеличивая \(y\) на 1) за цену \(x^2\).
- Если \(x<N\), Беси может переместиться в следующую строку
(увеличивая \(x\) на 1) за цену \(c_y\).
ВАм даются \(Q\) (\(1\le Q\le 2\cdot 10^5\)) независимых запросов, каждый в виде
\((x_i,y_i)\) (\(x_i\in [1,N], y_i\in [1,M]\)),
вычислите минимально возможную цену для Беси переместиться из \((1,1)\) в \((x_i,y_i)\).
compute the minimum possible total
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\) и
\(M\).
Вторая строка содержит \(M\) разделённых пробелом целых чисел \(c_1,c_2,\ldots,c_M\).
Третья строка содержит \(Q\).
Каждая из последующих \(Q\) строк содержит два целых числа \(x_i\) и \(y_i\).
ФОРМАТ ВЫВОДА (на экран / stdout):
\(Q\) строк, содержащих ответы на каждый запрос.
Заметим, что ответ требует использования 64-битного целого, например
"long long" в C/C++).
Ваш ответ: