You are given an integer array nums and an integer x.

You start at index $0$ of the array and can visit a sequence of indices with strictly increasing values, starting at index $0$.

When moving from index i to index j (where i < j), you add nums[j] to your total score. However, if nums[i] and nums[j] have different parities (one is odd and the other is even), you must subtract x from your score as a penalty.

Initially, your score is equal to nums[0].

Return the maximum score you can achieve by choosing an optimal sequence of visited indices.

Constraints:

• $2 \leq$ nums.length $\leq 10^5$

• $1 \leq$ nums[i], x $\leq 10^6$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.