C'est la semaine de la mode, et vous essayez les dernières ceintures design de Paris. Malheureusement, aucune des ceintures n'est à votre taille, ce qui indique clairement une chose : vous avez besoin de faire plus d'exercice.

Vous décidez que le meilleur moment pour faire de l'exercice est lors de chacun de vos trajets de retour à la maison en tramway. Le tramway va en ligne droite de l'école à la maison, et la ligne contient plusieurs arrêts. Vous pouvez faire de l'exercice en descendant du tramway à un arrêt, marchant vers un autre stop plus loin le long de la ligne, puis remontant dans le prochain tramway qui passe par là. Vous pouvez faire ceci autant de fois que vous souhaitez (utiliser le tramway, marcher, utiliser le tramway, et ainsi de suite). Vous pouvez choisir de commencer le trajet en marchant, et vous pouvez décider de descendre d'un tramway à un arrêt, et finir le trajet à pied.

Les tramways passent toutes les T minutes, et le premier tramway quitte votre école précisément quand vous commencez votre trajet. Les tramways se déplacent à vitesse fixe, et vous marchez également à une vitesse fixe, plus lente. Vous ne pouvez marcher que vers chez vous (vous ne pouvez pas retourner vers l'école ni tourner en rond). Si vous marchez de l'arrêt A à l'arrêt B et attrapez le tramway suivant, vous attendez simplement à l'arrêt B et écoutez votre lecteur de mp3 jusqu'à-ce que le prochain tramway passe. Si vous arrivez à l'arrêt B précisément au moment où un tramway passe, vous pouvez monter à bord.

Après avoir parcouru quelques magazines de santé, vous décidez que vous avez besoin de marcher au moins K mètres lors de vorte trajet. Votre objectif est de trouver le temps de trajet le plus petit possible, allant du début à la fin et qui respecte les conditions décrites plus haut.

Exemple

Considérez la ligne de tramway illustrée ci-dessous. Elle commence par l'école du côté gauche, après laquelle se trouvent S=6 arrêts. Les distances entre les arrêts consécutifs sont indiquées sur le diagramme, et votre maison se trouve au tout dernier arrêt.

Supposez que la gestion du tramway soit très performante et que les tramway passent toutes les 30 secondes, i.e., toutes les T=30 000 millisecondes. Les tramways prennent M_t=1 millisecondes pour se déplacer d'un mètre et il ne vous faut que M_w=100 millisecondes pour marcher un mètre. Votre régime minceur vous impose de marcher au moins K=870 mètres durant votre trajet.

Une stratégie optimale pour rentrer chez vous est la suivante :

Action	Arrêts	Distance	Temps
Utiliser le tramway	Ecole--1	450m	450ms
Marcher	1--2	300m	30 000ms
Attendre le tramway	2		300ms
Utiliser le tramway	2--3	450m	450ms
Marcher	3--5	600m	60 000ms
Attendre le tramway	5		600ms
Utiliser le tramway	5--6	450m	450ms
Total			92 250ms

Votre distance totale de marche selon ce plan est de 900m, ce qui est suffisant car c'est plus que les K=870m requis. Le temps de trajet total est de 92 250 millisecondes.

Tous les temps ci-dessous sont mesurés en millisecondes et toutes les distances sont mesurées en mètres.

• 30 000 <= T <= 1 000 000, où T est le temps entre chaque tramway et le suivant;
• 1 <= M_t < M_w <= 100, où M_t est le temps nécessaire à un tramway pour avancer d'un mètre et M_w est le temps dont vous avez besoin pour marcher d'un mètre;
• 1 <= K <= 10 000, où K est la distance minimale que vous devez marcher;
• 1 <= S <= 100, où S est le nombre total d'arrêts de tramway (sans compter l'école où votre trajet commence);
• Il n'y a jamais deux arrêts séparés de plus de 1 000 mètres;
• Le dernier arrêt est au moins à K mètres de l'école (i.e., il est possible de marcher assez pour obtenir l'exercice dont vous avez besoin).

De plus, 30% des points seront attribués à des tests dans lesquels la distance de marche minimale satisfait K <= 2 000.

Votre programme doit lire sur l'entrée standard. La première ligne contiendra un simple entier T, qui donne le temps entre chaque tramway et le suivant. La deuxième ligne contiendra les deux entiers M_t et M_w séparés par un espace, donnant le temps nécessaire à un tramway pour se déplacer d'un mètre, et le temps qu'il vous faut pour marcher un mètre. La troisième ligne contiendra un simple entier K, donnant la distance minimale que vous avez besoin de marcher.

La quatrième ligne de l'entrée contiendra l'entier S, donnant le nombre total d'arrêts de tramway (à l'exception de l'école où le trajet commence). Les S lignes suivantes donnent les positions des arrêts individuels dans l'ordre, de l'école à votre maison. La i^ème de ces lignes contiendra l'entier D_i, donnant la distance de l'école au i^ème arrêt. Votre maison est au dernier de ces arrêts.

Une fois de plus, tous les temps sont mesurés en millisecondes et toutes les distances sont mesurées en mètres.

Votre programme doit écrire une simple ligne sur la sortie standard, contenant un entier : la durée totale de trajet la plus courte possible, mesurée en millisecondes.

30000
1 100
870
6
450
750
1200
1740
1800
2250

92250

Calcul du score

Le score pour chaque test d'entrée sera de 100% si la bonne réponse est fournie, et 0% sinon.