| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 3 | 2 | 2 | 66.667% |
Доктор Стрэндж любит читать и изучать новые заклинания. В его любимом книжном магазине <<У Дормамму>> акция! Но доктор попал во временную петлю, и у него не хватает времени, поэтому все книги он решил заказать с доставкой через интернет.
Доктор планирует купить $n$ различных книг. По акции при покупке $w + q$ и более книг $w$ самых дешевых из них достаются бесплатно. Доставка одного заказа стоит $e$ монет. Герой может заказать набор различных книг, которых нет в других заказах. Количество книг в одном заказе неограниченно.
К сожалению, доктор забыл значение $q$. Помогите великому магу. Для каждого значения $q$ от $1$ до $n$ найдите минимальное количество монет, которое необходимо потратить, чтобы купить все $n$ книг.
В первой строке заданы числа $n$, $e$ и $w$ --- количество книг, цена доставки и количество бесплатных книг ($1 \le w \le n \le 3 \cdot 10^5$; $1 \le e \le 10^6$).
Далее следует $n$ строк. В каждой записано число $t$ --- цена i-ой книги ($1 \le t \le 10^6$).
Выведите $n$ чисел --- минимальное количество монет, необходимое для покупки всех книг, при значении $q$ от $1$ до $n$.
5 1 1 1 2 3 4 5
12 14 15 15 16
6 3 2 2 1 3 2 1 5
13 15 15 15 17 17