Ein Unterhaltungssender überträgt die Show „Колесо Фортуны“. Während des Spiels drehen die Teilnehmer ein großes Rad, das in Sektoren unterteilt ist. In jedem Sektor steht eine Zahl. Nachdem das Rad zum Stillstand gekommen ist, zeigt ein besonderer Zeiger auf einen der Sektoren. Die Zahl in diesem Sektor bestimmt den Gewinn des Spielers.
Ein junger Teilnehmer hat bemerkt, dass das Rad beim Drehen langsamer wird, weil der Zeiger an Vorsprüngen zwischen den Sektoren hängen bleibt. Dreht sich das Rad mit einer Winkelgeschwindigkeit von $v$ Grad pro Sekunde und stößt der Zeiger beim Übergang vom Sektor $X$ zum nächsten Sektor an einen solchen Vorsprung, verringert sich die aktuelle Winkelgeschwindigkeit des Rades um $k$ Grad pro Sekunde. Falls $v\le k$ gilt, kann das Rad das Hindernis nicht überwinden und bleibt stehen. Der Zeiger zeigt dann auf den Sektor $X$.
Der junge Teilnehmer möchte das Rad drehen. Er kennt die Reihenfolge der Sektoren und möchte eine Anfangsgeschwindigkeit wählen, bei der der Zeiger nach dem Stillstand auf eine möglichst große Zahl zeigt. Das Rad kann in beiden Richtungen gedreht werden, und seine anfängliche Winkelgeschwindigkeit darf zwischen $a$ und $b$ Grad pro Sekunde liegen.
Schreibe ein Programm, das aus der gegebenen Anordnung der Zahlen in den Sektoren, der minimalen und maximalen anfänglichen Winkelgeschwindigkeit sowie der Geschwindigkeitsabnahme beim Überqueren einer Sektorgrenze den maximalen Gewinn berechnet.
Eingabe
Die erste Zeile der Eingabedatei enthält eine ganze Zahl $n$, die Anzahl der Sektoren des Rades ($3\le n\le100$).
Die zweite Zeile der Eingabedatei enthält $n$ positive ganze Zahlen, die jeweils höchstens $1000$ sind: die Zahlen in den Sektoren des Rades. Sie sind in der Reihenfolge der Sektoren im Uhrzeigersinn angegeben. Anfangs zeigt der Zeiger auf die erste Zahl.
Die dritte Zeile enthält drei ganze Zahlen $a$, $b$ und $k$ ($1\le a\le b\le10^9$, $1\le k\le10^9$).
Ausgabe
Die Ausgabedatei soll eine ganze Zahl enthalten: den maximalen Gewinn.
Beispiele
Eingabe 1
5 1 2 3 4 5 3 5 2
Ausgabe 1
5
Eingabe 2
5 1 2 3 4 5 15 15 2
Ausgabe 2
4
Eingabe 3
5 5 4 3 2 1 2 5 2
Ausgabe 3
5
Hinweis
Im ersten Beispiel gibt es folgende Möglichkeiten: Eine Anfangsgeschwindigkeit von $3$ oder $4$ lässt den Zeiger eine Sektorgrenze überwinden; bei einer Anfangsgeschwindigkeit von $5$ überwindet er zwei Sektorgrenzen. Im ersten Fall beträgt der Gewinn $2$, wenn das Rad in einer Richtung gedreht wird, und $5$ bei der entgegengesetzten Richtung. Im zweiten Fall beträgt der Gewinn $3$ in einer Richtung und $4$ in der anderen.
Im zweiten Beispiel ist nur eine Anfangsgeschwindigkeit möglich: $15$ Grad pro Sekunde. Dabei überwindet der Zeiger sieben Sektorgrenzen. Wird das Rad in einer Richtung gedreht, beträgt der Gewinn $4$; bei der entgegengesetzten Richtung beträgt er $3$.
Im dritten Beispiel schließlich beträgt die optimale Anfangsgeschwindigkeit $2$ Grad pro Sekunde. Dann kann der Zeiger keine einzige Sektorgrenze überwinden, und der Gewinn beträgt $5$.
Hinweis
Lösungen, die für die Tests mit $1\le a\le b\le1000$ korrekt sind, werden mit bis zu 50 Punkten bewertet.