4. Zápolenie o cukríky

Jedno pomalé štvrtkové popoludnie Kuko zase raz dostal chuť na cukríky. V tú ranu vošiel do miestnosti Mišo s jeho obľubeným balením všetkých chutí. Kukovi v hlave vzkrsol nápad – stavil sa s Mišom o cukrík, že proti nemu vyhrá partiu hry Go. Tak hrali jednu hru, dve hry, až napokon za svitu posledných lúčov zapadajúceho slnka vyprázdnili celý sáčok.

Kukovi sa podarilo vyhrať každú jednu hru. Teraz, keď už nemá žiadne ďalšie cukríky na zjedenie, začal uvažovať, či by mu celé balenie nechutilo viac, ak by niektoré hry nechal vyhrať Miša.

Kukove chuťové poháriky totiž fungujú prazvláštne. Ak si dá len jeden cukrík, je mu jedno aký bude, všetky mu budú chutiť rovnako. Ak ale zje dva rovnaké po sebe, situácia je trochu zložitejšia. Niektorých chutí by sa nevedel nabažiť ani keby ste mu doviezli plný kamión, pri iných by druhý rovnaký cukrík zjedol len pri použití násilia.

Teraz by od vás chcel vedieť, ako najviac mu mohlo Mišove balenie chutiť, ak by niektoré hry nevyhral.

Úloha

Na vstupe máte postupnosť cukríkov dĺžky \(n\), o ktoré postupne Kuko s Mišom bojovali. Pre každý typ cukríka \(i\), tiež viete, akú má chutnosť, ak je zjedený po cukríku rovnakého typu – túto chutnosť nazveme \(b_i\). Tiež viete, akú má chutnosť cukrík, ak je zjedený po cukríku iného typu – chutnosť \(c\). Táto chutnosť je rovnaká pre všetky typy cukríkov.

Prvý cukrík má chutnosť rovnakú, ako keby bol zjedený po cukríku iného typu (teda \(c\)), chutnosť každého ďalšieho cukríka závisí na type posledného zjedeného cukríka.

Nájdite chutnosť najchutnejšej podpostupnosti cukríkov (nie nutne súvislej). Chutnosť podpostupnosti je rovná súčtu chutností jednotlivých zjedených cukríkov.

Formát vstupu

V prvom riadku vstupu sú kladné, medzerou oddelené čísla \(n\), udávajúce počet cukríkov, a \(m\), udávajúce počet typov cukríkov. Platí, že \(1 \leq m \leq n \leq 1\,000\,000\)

V nasledujúcom riadku sa nachádza \(n\) medzerou oddelených čísel \(a_i\) (\(1 \leq a_i \leq m\)) – typ \(i\)-teho cukríka.

V ďalšom riadku nasleduje \(m\) medzerou oddelených čísel \(b_i\) (\(0 \leq b_i \leq 10^9\)) – chutnosť cukríka typu \(i\), ak bol zjedený hneď po cukríku rovnakého typu.

V poslednom riadku je jedno kladné číslo \(c\) (\(0 \leq c \leq 10^9\)) – chutnosť cukríka, ak bol zjedený hneď po cukríku iného typu, alebo je to prvý zjedený cukrík.

Všimnite si, že súčet chutností cukríkov ľahko presiahne \(2^{31} - 1 \approx 2 \cdot 10^9\), čo je najväčšie číslo, ktoré sa dá uložiť v \(32\)-bitovej premennej so znamienkom. Použite preto \(64\)-bitové premenné typu long long v C++ a Int64 v Pascale.

Formát výstupu

Na jediný riadok vypíšte chutnosť najchutnejšej podpostupnosti cukríkov, akú vie Kuko dosiahnuť.

Príklad

Input:

5 3
1 2 3 3 2
3 7 1
2

Output:

11

Najchutnejšia podpostupnosť je \(1, 2, 2\), pričom jednotlivé chutnosti curíkov sú \(2, 2, 7\). Prvý a druhý cukrík majú obidva chutnosť \(c = 2\), keďže pred nimi nebol zjedený cukrík rovnakého typu. Všimnite si tiež, že ak by Kuko zjedol všetky cukríky, celková chutnosť by bola menšia, konkrétne \(2+2+2+1+2 = 9\).