Problem D
Radio Commercials
Our favorite Onid Pizza would like to have a commercial aired in a radio. Since they are close to KTH, they want to attract mainly students. It’s not a good idea to have the commercial aired between 8 am and 5 pm, because most of the students are in the school and don’t listen to the radio. Onid made a survey and now they know how many students listen to the radio at each point of the day.
They also know that if each student listens to a commercial, he or she will spend one Swedish crown on pizza in expectation. Thus if 100 students listen to a commercial, Onid will increase their income by 100 crowns on average from selling more pizza.
Of course, Onid Pizza has to pay a fixed amount every time the commercial is played. The radio has a commercial break every 15 minutes. Unfortunately, Onid can choose only one continuous sequence of commercial breaks, for example all breaks from 5 pm to 8 pm. Help them to choose a continuous sequence of commercial breaks such that their profit is maximal.
Input
The first line of the input contains two space separated positive integers $N, P$ – the total number of commercial breaks in a day and the price of one commercial break. You can assume that $N \le 100\, 000$ and $P \le 1\, 000$. On the next line there are $N$ space-separated integers – the $i$’th integer denotes how many students listen to the $i$-th commercial break. There are always at most $2\, 000$ students listening.
Output
Output contains one line with one integer – the biggest expected extra profit Onid can get by selecting a continuous sequence of commercial breaks.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 20 18 35 6 80 15 21 |
61 |
