Problem Brief

Starlight

The presented problem involves an astral constellation, depicted as an array of n integers where each representing the luminosity of a star. The beauty of this constellation is determined by the maximum overall sum of luminance of any consecutive light cluster. It could range from none of the stars to all the stars of the constellation.

Bear in mind an example of a constellation represented by the array [20, -9, 0, 4, 0] the beauty of this constellation is 21. On the other hand, a constellation represented by [-3, -5, -1, -4] has a beauty of 0 units.

Assume that you are equipped with a cosmic amplifier, having a power multiplier of z. This device allows you to magnify the luminescence of any chosen segment within the constellation by a factor of z. Here comes the challenge: You can use this amplification at most once, so the task is to decipher how to maximize the beauty constellation after this amplification procedure.

Function Description

Complete the function enhanceLuminescence.

enhanceLuminescence has the following parameters:

int arr[n]: represents the individual luminescence of each celestial entity within the constellation.
int z: the power multiplier that can be applied to a chosen sequence within the constellation.

Returns

int: the maximum possible beauty of the arrangement after applying the amplification.

1Example 1

Input

arr = [3, 2], z = 2

Output

Explanation

For the constellation [3, 2], if we apply a power multiplier of 2 to the entire constellation, we get an amplified luminescence of [6, 4] and a beauty of 10.

2Example 2

Input

arr = [-5, -9, -2, 1, -6], z = -3

Output

Explanation

Here we multiply the last [-2, 1, -6] with the magnification factor. The final magnified array looks like [-5, -9, 6, -3, 18]. Hence the beauty of this arrangement is the sum of [9, 6, -3, 18] which is 30.

3Example 3

Input

arr = [1, 2, 4, 5], z = -2

Output

Explanation

Here all the elements in the array are positive hence we do not apply the magnification and the beauty of the arrangement is the sum of [1, 2, 4, 5] which is 12.

Constraints

Limits and guarantees your solution can rely on.

The size of the stars array, n, lies in the range of 1 ≤ n ≤ 2 * 10^5.
The elements of the stars array, a1, a2, a3, ..., lie in the range 10^-9 ≤ ai ≤ 10^9.
The amplification power, z, lies in the range -100 ≤ z ≤ 100.