12153. Подорож
Степан планує \(N\)-денну поїздку потягом.
За кожну добу він може оплатити звичайний тариф або скористатися одноденним абонементом.
Тут для \(1≤i≤N\) звичайний тариф на \(i\)-й день подорожі становить \(F_i\).
З іншого боку, партія одноденних абонементів \(D\) продається за \(P\). Ви можете придбати скільки завгодно абонементів, але лише в одиницях \(D\). Кожен купленмй абонемент можна використати в будь-який день, і добре залишити трохи наприкінці подорожі.
Знайдіть мінімально можливу загальну вартість для \(N\)-денної поїздки, тобто вартість придбання одноденних абонементів плюс загальний звичайний тариф за дні, на які не діють одноденні абонементи.
Обмеження
- \(1≤N≤2×10^5\)
- \(1≤D≤2×10^5\)
- \(1≤P≤10^9\)
- \(1≤F_i ≤10^9\)
- Усі вхідні значення є цілими числами.
Формат вхідних даних
Перший рядок містить цілі числа \(N,D,P\).
Наступний рядок містить цілі числа \(F_i\).
Формат вихідних даних
У вихідний потік виведіть відповідь.
Приклад вхідних даних
5 2 10
7 1 6 3 6Приклад вихідних даних
20Якщо він придбає лише одну партію одноденних абонементів і використає їх протягом першого та третього днів, загальна вартість становитиме ( 10 × 1 ) + ( 0 + 1 + 0 + 3 + 6 ) = 20 , що є мінімальною необхідною ціною.
Приклад вхідних даних
3 1 10
1 2 3Приклад вихідних даних
6Приклад вхідних даних
8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000Приклад вихідних даних
3000000000
Коментарі
Вибачте, а чи є тут можливість видалити коментар?
Може лише адмін. Зайві коментарі періодично видаляються