Problem D
Börsen

Evelina vill bli rik och tänker börja spekulera på börsen. Egentligen är hon dock rätt ointresserad av ekonomi och orkar aldrig läsa mer än den första aktiekursen i tidningen. Men, tänker hon, det är ni andra som krånglar till det. Om man bara köper och säljer i rätt lägen kan man ju lika väl tjäna pengar på detta enda företag, som vi kan kalla $A$. Genom att ständigt fråga sina vänner hur mycket fiskbullar de äter lär hon sig att förutsäga exakt hur $A$:s aktiekurs kommer att variera under $N$ dagar framåt. Skriv ett program som beräknar hur mycket pengar hon har i slutet av denna period om hon hade 100 kronor från början och investerar optimalt. Hon kan aldrig låna pengar utan endast använda sina egna.

Aktiekursen uppdateras en gång om dagen och är densamma för köp och försäljning. Varje dag kan Evelina antingen köpa valfri mängd aktier, sälja valfri mängd aktier eller inte göra någonting. Mängden hon köper eller säljer behöver inte vara ett heltal. För varje transaktion hon gör måste hon betala en fast avgift. Avgiften betalas med kontanter, d.v.s. innan hon köper aktier måste hon först betala avgiften, och efter att hon har sålt aktier måste hon betala avgiften.

Indata

På första raden står ett heltal $N$ ($2 \le N \le 100\, 000$), antalet dagar. På andra raden står ett flyttal $Q$ ($0 \le Q \le 100$), avgiften i kronor per transaktion. Därefter följer $N$ rader med vardera ett flyttal, aktiekursen för dag 1, dag 2, o.s.v., t.o.m. dag $N$. Kursen ligger alltid mellan $1$ och $1\, 000$ kr per aktie.

6
2.3
75.6
86.2
83.1
91.3
72.5
95.7

147.3742