Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.
is a good boy. He loves programming and array very much. In this quarantine, he solves programming problems on different online judges all the time. Sometimes annoys his friends by asking them to solve some hard problems. For this reason, his friends don’t like him very much.
One day his friend came to his house for a visit. became very happy and immediately started discussing a very hard problem of arrays with . Soon felt uncomfortable. He broke into tears as he couldn’t bear the pain. After some time ran away from home.
This isn’t a big deal for you. But you are invited to upcoming birthday party next week. Where he may annoy you by discussing the same problem. It is better to practice it beforehand. Let’s take a look at the problem on which cried.
You will be given an array of size . You have to group the array in a specific manner. A group must be formed in sequential order. After selecting a group, the array must be updated before calculating the group cost.
You have to maximize the summation of the costs of all groups you have formed . What do you think, can you solve it?
The first line of the input contains two integers , denoting the length of the array and , denoting the magical value.
The second line contains integers , where is the element of array .
In a single line, output the maximum possible value.
Input | Output |
---|---|
5 10 3 4 2 4 5 | 39 |
Explanation Then the array become: Suppose group will be formed index to index , Then . Now, . So, array will be . The second group cost will be . Then the array become: Now, the group will be formed index 1 to index 1. Now, . So, array will be . The third group cost will be . Then the array is empty. And the summation of all the three group cost is, |
Login to submit