pix

Robotul Vasile s-a angajat la un depozit de pixuri. Aici pixurile sunt ambalate în cutii. Există $N$ tipuri de cutii; într-o cutie de tipul $i$ ($1 \leq i \leq N$) sunt ambalate exact $nr_i$ pixuri ($nr_1 \leq nr_2 \leq \cdots \leq nr_N$). În depozit există un număr atât de mare de cutii de fiecare tip încât Vasile poate utiliza oricâte cutii doreşte, de orice tip.
Sarcina robotului Vasile este să livreze pixurile comandate de diferite firme de birotică. El nu ştie câte pixuri va avea de livrat la următoarea comandă, dar ştie că vor fi cel mult $Vmax$ pixuri. Ca urmare, pentru a fi eficient, robotul Vasile vrea să îşi pregătească în camera de livrare un număr minim de cutii de pixuri astfel încât să poată livra orice număr de pixuri cuprins între $1$ şi $Vmax$ folosind cutiile pregătite, evident, fără a deschide cutiile.

Cerință

Scrieţi un program care citeşte valorile $N$, $nr_1$, $nr_2$, … $nr_N$ şi $Vmax$ și determină numărul minim de cutii pe care robotul Vasile trebuie să le pregătească în camera de livrare astfel încât să poată livra orice număr de pixuri cuprins între $1$ şi $Vmax$, fără a deschide nicio cutie.

Date de intrare

Fișierul de intrare pix.in conține pe prima linie numărul natural $N$ reprezentând numărul de tipuri de cutii. Pe a doua linie se află $N$ numere naturale în ordine crescătoare, separate prin câte un spaţiu, $nr_1$, $nr_2$, …, $nr_N$ reprezentând numărul pixuri ambalate în fiecare tip de cutie. Pe a treia linie se află numărul natural $Vmax$ cu semnificația din enunț.

Date de ieșire

Fişierul de ieşire pix.out va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul minim de cutii pe care robotul Vasile trebuie să le pregătească în camera de livrare astfel încât să poată livra orice număr de pixuri cuprins între $1$ şi $Vmax$.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$;
• $1 \leq Vmax, nr_i \leq 10^{12}$, pentru $1 \leq i \leq N$;
• Se garantează că pentru toate datele de test există soluţie.

Exemplu

pix.in

4
1 2 3 5
15

pix.out

5

Explicație

Numărul minim de cutii pe care trebuie să le pregătească Vasile este $5$ (o cutie de tipul $1$, două de tipul $2$ şi două de tipul $4$, numărul de pixuri din aceste cutii fiind $1, 2, 2, 5, 5$)
El poate astfel livra orice număr de pixuri între $1$ şi $15$, o modalitate posibilă fiind:

• $1$: cutia de tip $1$;
• $2$: o cutie de tip $2$;
• $3$: o cutie de tip $1$ şi o cutie de tip $2$;
• $4$: două cutii de tip $2$;
• $5$: o cutie de tip $4$;
• $6$: o cutie de tip $1$ şi o cutie de tip $4$;
• $7$: o cutie de tip $2$ şi o cutie de tip $4$;
• $8$: câte o cutie de tipurile $1, 2, 4$;
• $9$: o cutie de tip $4$ şi două cutii de tip $2$;
• $10$: două cutii de tip $4$;
• $11$: două cutii de tip $4$ şi o cutie de tip $1$;
• $12$: două cutii de tip $4$ şi o cutie de tip $2$;
• $13$: două cutii de tip $4$, o cutie de tip $2$ şi o cutie de tip $1$;
• $14$: două cutii de tip $4$ şi două cutii de tip $2$;
• $15$: toate cutiile.

Aceasta nu este singura posibilitate de a alege un număr minim de cutii pentru a obține toate valorile de la $1$ la $15$.