Вы зашли в ближайший магазин, чтобы купить несколько плиток шоколада. В магазине продаются \(n\) плиток, \(i\)-я стоит \(a_i\) монет (и вы хотите купить их все).
У вас есть \(m\) разных купонов, позволяющих покупать шоколадки на особых условиях. \(i\)-й купон позволяет купить \(q_i\) шоколадок, при этом заплатив только за \(q_i - 1\) наиболее дорогих из них (то есть самая дешевая из \(q_i\) шоколадок вам достанется бесплатно).
Вы можете использовать только один купон; если вы используете купон \(i\), вы должны выбрать \(q_i\) шоколадок, которые вы купите по купону, а все остальные \(n - q_i\) плиток вы купите без каких-либо скидок.
Чтобы понять, какой купон стоит использовать, вы хотите для каждого купона узнать, какое минимальное количество денег вам придется потратить, если вы используете его оптимально.
Выходные данные
Выведите \(m\) целых чисел, \(i\)-е из которых должно быть равно минимальному количеству монет, которые вы должны заплатить, если вы купите \(q_i\) шоколадок при помощи \(i\)-го купона, а все остальные — по их полной цене.
Примечание
Рассмотрим первый пример.
Если мы используем первый купон, можно выбрать шоколадки под номерами \(1\), \(6\) и \(7\), и мы заплатим \(18\) монет за них и \(9\) монет за все остальные.
Если мы используем второй купон, можно выбрать шоколадки под номерами \(1\), \(5\), \(6\) и \(7\), и мы заплатим \(25\) монет за них и \(5\) монет за все остальные.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
7 1 3 1 4 10 8
2
3 4
|
27
30
|