Maximum Profit with Transaction Fee

You are given the daily prices of a stock for n consecutive days and a transaction fee f. Your task is to compute the maximum profit you can achieve by making as many transactions as you like, with the condition that each transaction incurs the fee f.

You may complete as many transactions as you wish (i.e. buy one and sell one share of the stock multiple times) but you must sell the stock before you buy again. For each transaction, the transaction fee is deducted from the profit. The goal is to maximize the overall profit.

The state transition can be formulated as follows:

\( cash = \max(cash, hold + price - fee) \)

\( hold = \max(hold, cash - price) \)

Here, cash represents the maximum profit so far when you do not hold a stock, and hold represents the maximum profit so far when you do hold a stock.

Input/Output Requirements: The input is read from stdin and the output is printed to stdout.

inputFormat

The first line of input contains an integer n (the number of days). The second line contains n space-separated integers representing the stock prices on each day. The third line contains an integer fee representing the transaction fee.

outputFormat

Output a single integer which is the maximum profit achievable after processing all days.

## sample

6
1 3 2 8 4 9
2

8