Trên mặt phẳng toạ độ Oxy, bạn nhận được một hình vuông với cạnh song song với trục toạ độ, có góc trái dưới là ~(0, 0)~ và góc phải trên là ~(n, n)~. Hãy đếm xem có bao nhiêu điểm toạ độ nguyên nằm trong hoặc nằm trên biên hình vuông mà có khoảng cách Manhattan đến ~(x_0, y_0)~ đúng bằng ~k~.

Khoảng cách Manhattan giữa hai điểm ~(x, y)~ và ~(u, v)~ được tính bằng ~|x - u| + |y - v|~.

Input

Gồm một dòng duy nhất chứa bốn số nguyên ~n~, ~x_0~, ~y_0~, ~k~ (~1 \le n, k \le 10^{18}~; ~1 \le x_0, y_0 \le n~).

Output

In ra một số nguyên là số điểm toạ độ nguyên nằm trong hoặc nằm trên biên hình vuông mà có khoảng cách Manhattan đến ~(x_0, y_0)~ đúng bằng ~k~.

Scoring

• Subtask ~1~ (~30\%~ số điểm): ~n \le 10^3~.
• Subtask ~2~ (~30\%~ số điểm): ~k \le 10^5~.
• Subtask ~3~ (~40\%~ số điểm): Không có ràng buộc gì thêm.

Example

Input

4 1 1 2

Output

6