Egy $M$ ($1\le M\le 100000$, $M$ egész szám) hosszú falon $N$ ($1\le N\le 5000$) repedés keletkezett. Az egyszerűség kedvéért a repedéseket mint pontokat képzeljük el a falon, helyüket a fal egyik végétől valamilyen $x$ ($1\le x\le M$, egész) koordináták adják meg. Célunk az, hogy lefessük a fal minden repedését. Úgy festünk, hogy kinyitunk egy $w$ feliratú doboz festéket, amely pontosan $w$ hosszú falrész festésére alkalmas, majd a tartalmával lefestünk egy $x_0$ és $x_1$ koordinátákkal határolt falrészt ($w=x_1-x_0+1$). A kiválasztott tartományon belül természetesen lefestjük az ép falrészeket is ‐ akár többször is. Addig nyitunk ki újabb festékesdobozt és festünk, amíg minden repedést el nem tüntettünk. A festéshez minden $w$ ($1\le w\le M$) egész számra pontosan egy $w$ feliratú, és ismert $b_j$ árú doboz festék áll rendelkezésre. Egy hosszabb festés nem feltétlenül drágább, mint egy rövidebb, sőt egy nagyobb doboz festék ára lehet egy kisebb doboz festék árával egyenlő, vagy annál kisebb is. Fessük le a lehető legolcsóbban az összes repedést a falon.
A program olvassa be a standard input első sorából $N$-et és $M$-et, majd a következő $N$ sorból az $a_i$ egészeket, azaz a repedések helyét. A következő $M$ sorban rendre az egyes hosszokhoz tartozó festékes dobozok $b_j$ ára szerepel. Írjuk a standard output első sorába a minimális pénzt, amennyiből a festés megoldható. Helytakarékosság miatt a bemenetben az $N$, illetve az $M$ sorban lévő számokat / jellel elválasztva egy sorba írtuk.