Научимся решать для фиксированного q. Для этого отсортируем книги. Переберем сколько раз мы делаем заказ — пусть это число x. Поймем, что выгодной стратегией является покупка q + w самых дорогих еще не купленных книг x - 1 раз. Оставшиеся книги мы купим за 1 раз.
Теперь переберем Q. Переберем количество заказов, которые мы совершим пусть это x. Заметим, что x от 1 до .
Заметим, что книги мы всегда покупаем на отрезке в отсортированном порядке. Действительно, пусть мы купили k, по нашей жадности мы хотим купить следующим шагом еще q + w самый дорогих не купленных книг. Все эти книги следуют сразу после k-ой книги и лежат на отрезке длины q + w.
Теперь посчитаем префиксные суммы и за решим задачу для фиксированного q. Известно, что сумма
.