30072번 - Žygis 다국어

Žygeivis Vytis planuoja šiandien pasivaikščioti po kalnus. Pasitiesęs reljefo žemėlapį išsirinko maršrutą, kuris pavaizduotas kalnų aukščių seka. Keliaudamas nuo $i$-ojo taško iki $i + 1$-ojo, Vytis užlipa ar nusileidžia tik aukščių skirtumą, o jei taškai vienodame aukštyje – eina tiesiai. Vytis pradeda ir baigia žygį ties jūros lygiu (aukštis – $0$).

Vytis yra patyręs žygeivis ir žino, kad nueiti, užkopti ar nusileisti vieną metrą jam užtruks vieną laiko vienetą. Taip pat žino, kaip kinta jo energija:

• Papusryčiavęs jis įgauna energijos $E_0$.
• Kopdamas aukštyn kiekvienam metrui sueikvoja $E_u$ energijos.
• Leisdamasis žemyn kiekvienam metrui sueikvoja $E_n$ energijos.
• Vyčiui tiesiai eiti nesunku, tai eidamas tiesiai energijos nesueikvoja, tačiau jei visiškai neturi energijos, tiesiai žygiuoti jis negali.
• Jei Vytis žygio metu išnaudoja visą energiją, jis prisėda pailsėti. Kai ilsisi žygio metu, per vieną laiko vienetą įgauna $E_g$ energijos.

Pavyzdžiui, Vytis papusryčiavęs įgauna energijos $E_0 = 6$, užlipdamas sueikvoja $E_u = 3$, nulipdamas sueikvoja $E_n = 1$, ilsėdamasis įgauna $E_g = 1$ ir susiplanavo eiti tokiu kalnu:

1 pav. Dešinėje pavaizduotas aukštis, po paveikslėliu – maršruto taškai.

• Vytis užlips ant pirmojo taško savo maršrute, tam išnaudos $1$ laiko vienetą ir $3$ energijos vienetus.
• Vytis užlips ant antrojo taško savo maršrute, tam išnaudos $1$ laiko vienetą ir $3$ energijos vienetus.
• Čia Vytis sustos pailsėti, nes energijos nebeturi. Pailsėjęs vieną laiko momentą įgaus $1$ energijos vienetą.
• Vytis nueis prie trečiojo taško, tam sugaiš $1$ laiko momentą, bet neišnaudos energijos.
• Kadangi Vyčiui neužteks energijos nulipti nuo trečiojo taško, jam teks sustoti pailsėti dar vieną laiko momentą.
• Vytis nulips nuo trečiojo taško, tai užims $2$ laiko momentus ir tam sunaudos $2$ energijos vienetus.

Tad Vytis keliaus $7$ laiko momentus, iš kurių $5$ lips ar eis, ir $2$ ilsėsis.

Suskaičiuokite, kiek laiko truks Vyčio žygis, jei Vytis išvyksta į žygį papusryčiavęs.

Pirmojoje eilutėje pateikti keturi skaičiai, nurodantys:

• $E_0$ – Vyčio energija papusryčiavus;
• $E_u$ – kiek Vytis sunaudoja energijos užkopdamas vieną metrą aukštyn;
• $E_n$ – kiek Vytis sunaudoja energijos nusileisdamas vieną metrą žemyn;
• $E_g$ – kiek Vytis įgauna energijos per vieną laiko vienetą kai ilsisi.

Antrojoje eilutėje nurodytas maršruto ilgis $N$.

Tolimesnėse $N$ eilučių pateiktas maršrutas kalnų aukščių sekos $h_i$ pavidalu.

Išveskite sveikąjį skaičių, nurodantį, kiek laiko vienetų truks Vyčio žygis

• $1 ≤ E_0, E_g, E_u, E_n ≤ 1\,000$
• $1 ≤ N ≤ 100\,000$
• $1 ≤ h_i ≤ 10\,000$