ערוץ בידור משדר את התוכנית ״Колесо Фортуны״. במהלך המשחק המשתתפים מסובבים גלגל גדול המחולק לגזרות. בכל גזרה רשום מספר. לאחר שהגלגל נעצר, מחוג מיוחד מצביע על אחת הגזרות. המספר בגזרה זו קובע את סכום הזכייה של השחקן.

משתתף צעיר הבחין שהגלגל מאט במהלך הסיבוב מפני שהמחוג פוגע בבליטות שעל הגלגל, הנמצאות בין הגזרות. אם הגלגל מסתובב במהירות זוויתית של $v$ מעלות לשנייה, והמחוג פוגע בבליטה הבאה בזמן המעבר מגזרה $X$ לגזרה הבאה, המהירות הזוויתית הנוכחית של הגלגל קטנה ב־$k$ מעלות לשנייה. אם $v\le k$, הגלגל אינו יכול לעבור את המכשול ונעצר. במקרה זה המחוג מצביע על גזרה $X$.

המשתתף הצעיר עומד לסובב את הגלגל. בהכירו את סדר הגזרות, הוא רוצה לתת לגלגל מהירות התחלתית שתגרום למחוג להצביע על מספר גדול ככל האפשר לאחר העצירה. אפשר לסובב את הגלגל בכל אחד משני הכיוונים ולתת לו מהירות זוויתית התחלתית בין $a$ ל־$b$ מעלות לשנייה.

כתבו תוכנית המחשבת את סכום הזכייה המרבי לפי מיקומם של המספרים בגזרות, המהירות הזוויתית ההתחלתית המזערית והמרבית, וגודל ההאטה במעבר גבול בין גזרות.

קלט

השורה הראשונה בקובץ הקלט מכילה מספר שלם $n$, מספר הגזרות בגלגל ($3\le n\le100$).

השורה השנייה בקובץ הקלט מכילה $n$ מספרים שלמים חיוביים, שכל אחד מהם אינו גדול מ־$1000$: המספרים הרשומים בגזרות. המספרים נתונים לפי סדר הגזרות בכיוון השעון. בתחילה המחוג מצביע על המספר הראשון.

השורה השלישית מכילה שלושה מספרים שלמים: $a$, $b$ ו־$k$ ($1\le a\le b\le10^9$, $1\le k\le10^9$).

פלט

בקובץ הפלט יש להדפיס מספר שלם אחד: סכום הזכייה המרבי.

דוגמאות

קלט 1

5
1 2 3 4 5
3 5 2

פלט 1

5

קלט 2

5
1 2 3 4 5
15 15 2

פלט 2

4

קלט 3

5
5 4 3 2 1
2 5 2

פלט 3

5

הערה

בדוגמה הראשונה קיימות האפשרויות הבאות: אפשר לתת לגלגל מהירות התחלתית של $3$ או $4$, כך שהמחוג יעבור גבול אחד בין גזרות, או מהירות התחלתית של $5$, כך שיעבור שני גבולות. באפשרות הראשונה, סיבוב בכיוון אחד ייתן זכייה של $2$, וסיבוב בכיוון ההפוך ייתן זכייה של $5$. באפשרות השנייה, סיבוב בכיוון אחד ייתן זכייה של $3$, ובכיוון השני זכייה של $4$.

בדוגמה השנייה אפשרית רק מהירות התחלתית אחת, $15$ מעלות לשנייה. במקרה זה המחוג יעבור שבעה גבולות בין גזרות בזמן הסיבוב. סיבוב בכיוון אחד ייתן זכייה של $4$, ובכיוון ההפוך זכייה של $3$.

לבסוף, בדוגמה השלישית המהירות ההתחלתית המיטבית היא $2$ מעלות לשנייה. במקרה זה המחוג לא יוכל לעבור אף גבול בין גזרות, והזכייה תהיה $5$.

הערה

פתרונות נכונים למבחנים שבהם $1\le a\le b\le1000$ יקבלו עד $50$ נקודות.