Серега и Федя играют с функциями. Однажды им попалась очень интересная функция. Выглядит она так:
- f(1, j) = a[j], 1 ≤ j ≤ n.
- f(i, j) = min(f(i - 1, j), f(i - 1, j - 1)) + a[j], 2 ≤ i ≤ n, i ≤ j ≤ n.
Здесь a — целочисленный массив длины n.
Серега и Федя хотят знать значение этой функции в некоторых точках. Но вычислять вручную значения им не хочется. Поэтому они просят помощи у вас.
Выходные данные
Выведите m строк — ответы на запросы ребят.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
2 2 3 4 3 4
4
4 5
3 4
3 4
2 3
|
12
9
9
5
|
|
2
|
7
1 3 2 3 4 0 2
4
4 5
2 3
1 4
4 6
|
11
4
3
0
|