На столе перед Вами лежат n кучек камней размера a1, a2, ..., an.
За одно действие можно взять одну кучку и присоединить ее к другой. Причем при присоединении кучки i к кучке j размер кучки j увеличивается на текущий размер кучки i, а кучка i перестает существовать. Стоимость операции присоединения равна размеру присоединяемой кучки.
Ваша задача — определить минимальную стоимость, за которую можно собрать все камни в одну кучу.
Чтобы жизнь не казалась Вам слишком сладкой, кучки камней сговорились и решили, что каждая позволит совершить операцию присоединения к себе не более k раз (после чего только ее саму можно будет присоединить к другой кучке).
Более того, чтобы совсем сбить Вас с толку, кучки камней сообщили Вам q вариантов (необязательно различных) того, чему может быть равно k.
Ваша задача — найти минимальную стоимость для каждого из q вариантов.
Выходные данные
Выведите q чисел — ответы на запросы в том порядке, в котором запросы заданы во входных данных. Выведенные числа разделяйте пробельными символами.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примечание
В первом случае одним из способов достижения оптимального ответа является следующий: поочередно добавить 4-ю и 5-ю кучки ко 2-й; затем добавить 1-ю кучку к 3-й; добавить 2-ю кучку к 3-й. Первые две операции стоят по 1; третья — 2, четвертая — 5 (размер 2-й кучки после первых двух операций уже не 3, а 5).
Во втором случае можно добавить 2-ю кучку к 3-й (стоимость операции — 3); затем 1-ю к 3-й (стоимость — 2); далее 5-ю к 4-й (стоимость — 1); и, наконец, 4-ю к 3-й (стоимость — 2).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 3 4 1 1
2
2 3
|
9 8
|