Kalashnikov \(N\) күндік пойыз сапарын жоспарлап отыр. Әр күн үшін ол қарапайым жол жүру ақысы немесе бір күндік билет пайдалана алады.

Мұнда: \(1 \leq i \leq N\), \(i\)-ші күндегі қарапайым жол жүру ақысы \(F_i\) теңге. Екінші жағынан, \(D\) күнге арналған бір күндік билеттердің топтамасы \(P\) теңгеге сатылады. Сіз қалағаныңызша топтама сатып ала аласыз, бірақ тек \(D\) күндік бірліктермен. Әрбір сатып алынған билет кез келген күні қолданылуы мүмкін, және сапар соңында пайдаланылмай қалған билеттер болуы қалыпты жағдай.

\(N\) күндік сапардың ең аз жалпы құнын анықтаңыз, яғни бір күндік билеттердің құнын қосқанда, олармен қамтылмаған күндердегі қарапайым жол жүру ақысымен бірге.

Енгізу

• Бірінші қатарда: \(N\), \(D\), \(P\) — сәйкесінше сапардың ұзақтығы, бір күндік билеттер топтамасының көлемі және бір топтаманың бағасы.

• Екінші қатарда: \(F_1, F_2, \dots, F_N\) — әр күндегі қарапайым жол жүру ақысы.

Шектеулер:

• \(D \leq N \leq 200,000\)

• \(F[i], P \leq 10^9\)

Шығару

\(N\) күндік сапардың мүмкін болатын ең аз жалпы құнын басып шығарыңыз.

Бағалау жүйесі

Мәселе екі топтағы тестілерден тұрады:

• Бірінші топ: Қолмен жасалған тестілер — 50 ұпай.

• Екінші топ: Рандомды тестілер — 50 ұпай.

Топтың барлық тестілерін дұрыс шешкен жағдайда ғана сол топтың ұпайларын аласыз.

Мысалдар бағаланбайды.

Мысалдар

Енгізу 1

5 2 10
8 1 6 3 6

Жауап 1

20

Енгізу 2

3 1 10
3 2 1

Жауап 2

6