У Тимура есть лестница с \(n\) ступеньками. Ступенька \(i\) выше предыдущей на \(a_i\) метров. Первая ступенька на \(a_1\) метр выше земли, а земля находится на высоте \(0\) метров.
Лестница из первого примера. У Тимура есть \(q\) запросов, каждый из которых обозначается целым числом \(k_1, \dots, k_q\). Для каждого запроса \(k_i\) выведите максимально возможную высоту, на которую Тимур может подняться, поднимаясь по ступенькам, если длина его ног \(k_i\). Тимур может подняться на \(j\)-ю ступеньку только в том случае, если длина его ног не меньше \(a_j\). Другими словами, \(k_i \geq a_j\) для каждой ступеньки \(j\).
Обратите внимание, что вы должны ответить на каждый вопрос независимо.
Выходные данные
Для каждого набора выведите \(q\) целых чисел - ответ на каждый запрос.
Обратите внимание, что ответ на некоторые запросы не помещается в 32-битный целочисленный тип, поэтому вы должны использовать как минимум 64-битный целочисленный тип в вашем языке программирования (например, long long для C++).
Примечание
Рассмотрим первый пример, изображенный в условии.
- Если длина ног Тимура \(1\), то он может подняться только на ступеньку \(1\), поэтому максимальная высота, на которую он может забраться это \(1\) метр.
- Если длина ног Тимура \(2\) или \(4\), то он может подняться только по ступенькам \(1\), \(2\) и \(3\), поэтому максимальная высота, на которую он может забраться это \(1+2+1=4\) метра.
- Если длина ног Тимура составляет \(9\) или \(10\), то он может подняться по всей лестнице, так максимальная высота, на которую он может забраться это \(1+2+1+5=9\) метров.
В первом вопросе второго тестового примера у Тимура нет ног, поэтому он не может подняться даже на одну ступеньку.
:(
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4 5
1 2 1 5
1 2 4 9 10
2 2
1 1
0 1
3 1
1000000000 1000000000 1000000000
1000000000
|
1 4 4 9 9
0 2
3000000000
|