You are the VP of Engineering at a tech company, and you need to assemble an elite task force from your department to build a critical new product.

The department is organized in a strict top-down chain of command starting from a single Head of Engineering. To ensure focused leadership, no employee is allowed to directly manage more than two immediate subordinates. Each employee brings a unique, non-negative impact_score to the team based on their expertise.

You want to maximize the total impact_score of the assembled team, but you must strictly adhere to the following company policies:

1. Conflict of Interest: You cannot place an employee and their direct manager on the task force together.
2. Key Manager Penalty: Any manager who has exactly two direct reports is classified as a "Key Manager." If you place a Key Manager on the task force, their administrative burden reduces their effective impact_score by a constant penalty C. (An employee's effective score cannot drop below 0).
3. Leadership Vacuum: If you choose not to place a Key Manager on the task force, their absence creates a leadership vacuum. Consequently, you are permitted to select at most one of their two direct reports for the task force (you may also choose to select neither).

Employees with one or zero direct reports do not incur the Key Manager penalty, and skipping them does not trigger a leadership vacuum.

Given the starting employee at the top of the organizational chart and an integer C, return the maximum possible effective impact_score your task force can achieve.

Input Format

• Line 1: An integer n — the number of nodes present in the tree (this count includes null placeholders in the level-order layout). If n = 0, the organization is empty.
• Line 2: n space-separated node values given in level-order (breadth-first) traversal. The token null represents a missing direct report. (When n = 0, this line is empty.)
• Line 3: An integer C — the Key Manager penalty.

Output Format

• A single integer: the maximum possible effective total impact_score of the task force.

Sample Input 1

3
10 20 30
5

Sample Output 1

30

Explanation

Node 10 has exactly two direct reports (20 and 30), making it a Key Manager. Option 1 (Include Node 10): Its score becomes (10 - 5) = 5. By Policy 1, we cannot include 20 or 30. Total = 5. Option 2 (Exclude Node 10): By Policy 3 (Leadership Vacuum), we can select at most one direct report. We choose 30. Total = 30.

Constraints

• The number of actual employees (non-null nodes) is in the range [1, 10^4].
• 0 <= Node.val <= 10^4
• 0 <= C <= 10^4