Это сложная версия этой задачи. Единственное отличие в ограничении на \(k\) —количество подарков в акции. В этой версии \(2 \le k \le n\).
Вася пришел в магазин, чтобы купить подарки для своих друзей на Новый год. Оказалось, что ему очень повезло — именно сегодня в магазине проводится акция «\(k\) товаров по цене одного».
Благодаря этой акции Вася может купить ровно \(k\) любых подарков, заплатив только за самый дорогой из них. Вася решил воспользоваться этой возможностью и купить как можно больше подарков для своих друзей на деньги, которые у него имеются.
Более формально, для каждого подарка определена его цена \(a_i\) — количество монет, которое нужно потратить, чтобы приобрести этот подарок. Изначально, у Васи есть \(p\) монет. Он хочет приобрести максимальное количество подарков. Вася может сколько угодно раз выполнить одну из следующих операций.
- Вася может купить один любой подарок с номером \(i\), если у него в настоящий момент достаточно монет (то есть \(p \ge a_i\)). После покупки этого подарка, количество монет у Васи уменьшится на величину \(a_i\), то есть становится \(p := p - a_i\).
- Вася может купить подарок с номером \(i\), а также выбрать еще ровно \(k-1\) подарков, цены которых не превосходят \(a_i\), если у него в настоящий момент достаточно монет (то есть \(p \ge a_i\)). Таким образом он покупает все эти \(k\) подарков, а его количество монет уменьшается на величину \(a_i\), то есть становится \(p := p - a_i\).
Обратите внимание, что каждый подарок можно приобрести не больше одного раза.
Например, если в магазине сейчас есть \(n=5\) подарков, имеющих цены \(a_1=2, a_2=4, a_3=3, a_4=5, a_5=7\) соответственно, \(k=2\), а у Васи есть \(6\) монет, то он может купить суммарно \(3\) подарка. Подарок с номером \(1\) Вася купит, не используя акцию, и заплатит \(2\) монеты. Подарки с номерами \(2\) и \(3\) Вася купит используя акцию, и заплатит \(4\) монеты. Можно доказать, что приобрести больше подарков, имея шесть монет, Вася не может.
Помогите Васе узнать максимальное количество подарков, которые он может приобрести.