TheJobOverflow | Array Deletions

Difficulty Level : Medium

Submissions : 642

Asked In : Uber

Marks :10

: 10 | : 0

Given an array, you have to make some delete operations on it.

Delete any $$$p$$$ elements from it.
Now delete $$$q$$$ groups of $$$2$$$ consecutive elements from the remaining array
Now delete $$$r$$$ groups of 3 consecutive elements from the remaining array.

After all these operations, the sum of elements of the resultant array should be the maximum possible. Return this maximum value.

Input

The first line contains $$$4$$$ integers $$$n,p,q,r(1 \leq n \leq 100)$$$ and $$$0 \leq p,q,r \leq 30$$$.

The next line contains $$$n$$$ integers $$$a_1,a_2,...,a_n(-10^5 \leq a_i \leq 10^5)$$$ - the original array.

Output

Output a single integer - the maximum possible sum of remaining elements after performing the given operations.

Example

Input

9 1 1 1
3 1 0 5 1 6 5 -1 -100

Output

You need to login to view your submissions.

You need to login to view all submissions.

Language

Result : Executed

Result : Accepted

Test Cases :