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

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

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

Енгізу

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

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

Шектеулер:

• $D\le N\le 200,000$

• $F[i],P\le {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