У студентов одного неизвестного ПТУ нет обязательных занятий по физкультуре. Чтобы исправить это недоразумение, \(q\) студентов решили самостоятельно записаться в спортзал. В спортзале действует система абонементов на посещения, в \(i\)-й из \(n\) дней известна цена покупки абонемента \(a_i\). Разрешается покупать более одного абонемента за день.
Купленный в день \(i\) абонемент можно активировать как день \(i\), так и в любой день позднее. Каждый из абонементов после активации будет действовать \(k\) дней, то есть активированный в день \(t\) абонемент будет действовать в дни с номерами \(t, t + 1, \dots, t + k - 1\).
Известно, что \(j\)-й студент хочет посещать спортзал каждый день со дня \(l_j\) по день \(r_j\) включительно. Алгоритм похода в спортзал в некоторый день \(i\) (\(l_j \le i \le r_j\)) любого из студентов выглядит следующим образом:
- Студент подходит к кассе перед спортзалом и покупает несколько абонементов по цене \(a_i\) за штуку (возможно, не покупает ни одного).
- Если у студента есть хотя бы один действующий сегодня абонемент, то он просто проходит в спортзал. Иначе, он активирует один из купленных сегодня или ранее абонементов, и проходит в спортзал.
Заметим, что ни один студент не придет в спортзал раньше дня \(l_j\), а потому каждый студент обязательно купит не менее одного абонемента в день \(l_j\).
Помогите каждому студенту посчитать, какую минимальную сумму ему придется потратить, чтобы посещать зал в свои дни.