Пастбище Фермера Джона можно рассматривать решётку из квадратных ячеек
размером \(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++).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|